<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xml:lang="en" lang="en">
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>Structure and Interpretation of Computer Programs, 2e: 3.3</title>

<meta name="description" content="Structure and Interpretation of Computer Programs, 2e: 3.3" />
<meta name="keywords" content="Structure and Interpretation of Computer Programs, 2e: 3.3" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="Generator" content="texi2any" />
<meta charset="utf-8" />
<link href="index.xhtml#Top" rel="start" title="Top" />
<link href="Term-Index.xhtml#Term-Index" rel="index" title="Term Index" />
<link href="index.xhtml#SEC_Contents" rel="contents" title="Table of Contents" />
<link href="Chapter-3.xhtml#Chapter-3" rel="prev" title="Chapter 3" />
<link href="3_002e4.xhtml#g_t3_002e4" rel="next" title="3.4" />
<link href="3_002e2.xhtml#g_t3_002e2_002e4" rel="prev" title="3.2.4" />

<link href="css/style.css" rel="stylesheet" type="text/css" />
<link href="css/prettify.css" rel="stylesheet" type="text/css" />

<script src="js/jquery.min.js" type="text/javascript"></script>
<script src="js/footnotes.js" type="text/javascript"></script>
<script src="js/browsertest.js" type="text/javascript"></script>
</head>

<body>
<section><span class="top jump" title="Jump to top"><a href="#pagetop" accesskey="t">⇡</a></span><a id="pagetop"></a><a id="g_t3_002e3"></a>
<nav class="header">
<p>
Next: <a href="3_002e4.xhtml#g_t3_002e4" accesskey="n" rel="next">3.4</a>, Prev: <a href="3_002e2.xhtml#g_t3_002e2" accesskey="p" rel="prev">3.2</a>, Up: <a href="Chapter-3.xhtml#Chapter-3" accesskey="u" rel="prev">Chapter 3</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>
<a id="Modeling-with-Mutable-Data"></a>
<h3 class="section"><span class="secnum">3.3</span><span class="sectitle">Modeling with Mutable Data</span></h3>

<p><a href="Chapter-2.xhtml#Chapter-2">Chapter 2</a> dealt with compound data as a means for constructing computational
objects that have several parts, in order to model real-world objects that have
several aspects.  In that chapter we introduced the discipline of data
abstraction, according to which data structures are specified in terms of
constructors, which create data objects, and selectors, which access the parts
of compound data objects.  But we now know that there is another aspect of data
that chapter 2 did not address.  The desire to model systems composed of
objects that have changing state leads us to the need to modify compound data
objects, as well as to construct and select from them.  In order to model
compound objects with changing state, we will design data abstractions to
include, in addition to selectors and constructors, operations called
<a id="index-mutators"></a>
<em>mutators</em>, which modify data objects.  For instance, modeling a
banking system requires us to change account balances.  Thus, a data structure
for representing bank accounts might admit an operation
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">set-balance! ⟨</span><var><span class="pln">account</span></var><span class="pln">⟩ ⟨</span><var><span class="pln">new-value</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>that changes the balance of the designated account to the designated new value.
Data objects for which mutators are defined are known as <a id="index-mutable-data-objects"></a>
<em>mutable data objects</em>.
</p>
<p>Chapter 2 introduced pairs as a general-purpose “glue” for synthesizing
compound data.  We begin this section by defining basic mutators for pairs, so
that pairs can serve as building blocks for constructing mutable data objects.
These mutators greatly enhance the representational power of pairs, enabling us
to build data structures other than the sequences and trees that we worked with
in <a href="2_002e2.xhtml#g_t2_002e2">2.2</a>.  We also present some examples of simulations in which
complex systems are modeled as collections of objects with local state.
</p>

<a id="g_t3_002e3_002e1"></a>
<a id="Mutable-List-Structure"></a>
<h4 class="subsection"><span class="secnum">3.3.1</span><span class="sectitle">Mutable List Structure</span></h4>

<p>The basic operations on pairs—<code>cons</code>, <code>car</code>, and <code>cdr</code>—can
be used to construct list structure and to select parts from list structure,
but they are incapable of modifying list structure.  The same is true of the
list operations we have used so far, such as <code>append</code> and <code>list</code>,
since these can be defined in terms of <code>cons</code>, <code>car</code>, and <code>cdr</code>.
To modify list structures we need new operations.
</p>
<p>The primitive mutators for pairs are <code>set-car!</code> and
<code>set-cdr!</code>. <code>Set-car!</code> takes two arguments, the first of which must
be a pair.  It modifies this pair, replacing the <code>car</code> pointer by a
pointer to the second argument of <code>set-car!</code>.<a class="footnote_link" id="DOCF144" href="#FOOT144"><sup>144</sup></a>
</p>
<p>As an example, suppose that <code>x</code> is bound to the list <code>((a b) c d)</code>
and <code>y</code> to the list <code>(e f)</code> as illustrated in <a href="#Figure-3_002e12">Figure 3.12</a>.
Evaluating the expression <code> (set-car!  x y)</code> modifies the pair to which
<code>x</code> is bound, replacing its <code>car</code> by the value of <code>y</code>.  The
result of the operation is shown in <a href="#Figure-3_002e13">Figure 3.13</a>.  The structure <code>x</code>
has been modified and would now be printed as <code>((e f) c d)</code>.  The pairs
representing the list <code>(a b)</code>, identified by the pointer that was
replaced, are now detached from the original structure.<a class="footnote_link" id="DOCF145" href="#FOOT145"><sup>145</sup></a>
</p>
<figure class="float">
<a id="Figure-3_002e12"></a>
<object style="width: 48.18ex; height: 37.82ex;" data="fig/chap3/Fig3.12b.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.12:</strong> Lists <code>x</code>: <code>((a b) c d)</code> and <code>y</code>: <code>(e f)</code>.</p>
</figcaption>
</figure>

<figure class="float">
<a id="Figure-3_002e13"></a>
<object style="width: 48.18ex; height: 37.82ex;" data="fig/chap3/Fig3.13b.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.13:</strong> Effect of <code>(set-car! x y)</code> on the lists in <a href="#Figure-3_002e12">Figure 3.12</a>.</p>
</figcaption>
</figure>

<p>Compare <a href="#Figure-3_002e13">Figure 3.13</a> with <a href="#Figure-3_002e14">Figure 3.14</a>, which illustrates the result
of executing <code>(define z (cons y (cdr x)))</code> with <code>x</code> and <code>y</code>
bound to the original lists of <a href="#Figure-3_002e12">Figure 3.12</a>.  The variable <code>z</code> is now
bound to a new pair created by the <code>cons</code> operation; the list to which
<code>x</code> is bound is unchanged.
</p>
<figure class="float">
<a id="Figure-3_002e14"></a>
<object style="width: 48.18ex; height: 38.68ex;" data="fig/chap3/Fig3.14b.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.14:</strong> Effect of <code>(define z (cons y (cdr x)))</code> on the lists in <a href="#Figure-3_002e12">Figure 3.12</a>.</p>
</figcaption>
</figure>

<p>The <code>set-cdr!</code> operation is similar to <code>set-car!</code>.  The only
difference is that the <code>cdr</code> pointer of the pair, rather than the
<code>car</code> pointer, is replaced.  The effect of executing <code>(set-cdr! x y)</code>
on the lists of <a href="#Figure-3_002e12">Figure 3.12</a> is shown in <a href="#Figure-3_002e15">Figure 3.15</a>.  Here the
<code>cdr</code> pointer of <code>x</code> has been replaced by the pointer to <code>(e
f)</code>.  Also, the list <code>(c d)</code>, which used to be the <code>cdr</code> of <code>x</code>,
is now detached from the structure.
</p>
<figure class="float">
<a id="Figure-3_002e15"></a>
<object style="width: 48.18ex; height: 37.82ex;" data="fig/chap3/Fig3.15b.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.15:</strong> Effect of <code>(set-cdr! x y)</code> on the lists in <a href="#Figure-3_002e12">Figure 3.12</a>.</p>
</figcaption>
</figure>

<p><code>Cons</code> builds new list structure by creating new pairs, while
<code>set-car!</code> and <code>set-cdr!</code> modify existing pairs.  Indeed, we could
implement <code>cons</code> in terms of the two mutators, together with a procedure
<code>get-new-pair</code>, which returns a new pair that is not part of any existing
list structure.  We obtain the new pair, set its <code>car</code> and <code>cdr</code>
pointers to the designated objects, and return the new pair as the result of
the <code>cons</code>.<a class="footnote_link" id="DOCF146" href="#FOOT146"><sup>146</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> x y</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">new </span><span class="opn">(</span><span class="pln">get-new-pair</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">set-car! new x</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">set-cdr! new y</span><span class="clo">)</span><span class="pln">
    new</span><span class="clo">))</span></pre></div>

<blockquote>
<p><strong><a id="Exercise-3_002e12"></a>Exercise 3.12:</strong> The following procedure for
appending lists was introduced in <a href="2_002e2.xhtml#g_t2_002e2_002e1">2.2.1</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">append x y</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? x</span><span class="clo">)</span><span class="pln">
      y
      </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">append </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> x</span><span class="clo">)</span><span class="pln"> y</span><span class="clo">))))</span></pre></div>

<p><code>Append</code> forms a new list by successively <code>cons</code>ing the elements of
<code>x</code> onto <code>y</code>.  The procedure <code>append!</code> is similar to
<code>append</code>, but it is a mutator rather than a constructor.  It appends the
lists by splicing them together, modifying the final pair of <code>x</code> so that
its <code>cdr</code> is now <code>y</code>.  (It is an error to call <code>append!</code> with an
empty <code>x</code>.)
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">append! x y</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">set-cdr! </span><span class="opn">(</span><span class="pln">last-pair x</span><span class="clo">)</span><span class="pln"> y</span><span class="clo">)</span><span class="pln">
  x</span><span class="clo">)</span></pre></div>

<p>Here <code>last-pair</code> is a procedure that returns the last pair in its
argument:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">last-pair x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> x</span><span class="clo">))</span><span class="pln">
      x
      </span><span class="opn">(</span><span class="pln">last-pair </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> x</span><span class="clo">))))</span></pre></div>

<p>Consider the interaction
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> x </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'a</span><span class="pln"> </span><span class="lit">'b</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> y </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'c</span><span class="pln"> </span><span class="lit">'d</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> z </span><span class="opn">(</span><span class="pln">append x y</span><span class="clo">))</span><span class="pln">

z
</span><i><span class="opn">(</span><span class="pln">a b c d</span><span class="clo">)</span></i><span class="pln">

</span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> x</span><span class="clo">)</span><span class="pln">
⟨</span><var><span class="pln">response</span></var><span class="pln">⟩

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> w </span><span class="opn">(</span><span class="pln">append! x y</span><span class="clo">))</span><span class="pln">

w
</span><i><span class="opn">(</span><span class="pln">a b c d</span><span class="clo">)</span></i><span class="pln">

</span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> x</span><span class="clo">)</span><span class="pln">
⟨</span><var><span class="pln">response</span></var><span class="pln">⟩</span></pre></div>

<p>What are the missing <code>⟨</code><var>response</var><code>⟩</code>s?  Draw box-and-pointer diagrams to
explain your answer.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e13"></a>Exercise 3.13:</strong> Consider the following
<code>make-cycle</code> procedure, which uses the <code>last-pair</code> procedure defined
in <a href="#Exercise-3_002e12">Exercise 3.12</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-cycle x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">set-cdr! </span><span class="opn">(</span><span class="pln">last-pair x</span><span class="clo">)</span><span class="pln"> x</span><span class="clo">)</span><span class="pln">
  x</span><span class="clo">)</span></pre></div>

<p>Draw a box-and-pointer diagram that shows the structure <code>z</code> created by
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> z </span><span class="opn">(</span><span class="pln">make-cycle </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'a</span><span class="pln"> </span><span class="lit">'b</span><span class="pln"> </span><span class="lit">'c</span><span class="clo">)))</span></pre></div>

<p>What happens if we try to compute <code>(last-pair z)</code>?
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e14"></a>Exercise 3.14:</strong> The following procedure is quite
useful, although obscure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">mystery x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">loop x y</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? x</span><span class="clo">)</span><span class="pln">
        y
        </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">temp </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> x</span><span class="clo">)))</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">set-cdr! x y</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">loop temp x</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">loop x </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)))</span></pre></div>

<p><code>Loop</code> uses the “temporary” variable <code>temp</code> to hold the old value
of the <code>cdr</code> of <code>x</code>, since the <code>set-cdr!</code>  on the next line
destroys the <code>cdr</code>.  Explain what <code>mystery</code> does in general.  Suppose
<code>v</code> is defined by <code>(define v (list 'a 'b 'c 'd))</code>. Draw the
box-and-pointer diagram that represents the list to which <code>v</code> is bound.
Suppose that we now evaluate <code>(define w (mystery v))</code>. Draw
box-and-pointer diagrams that show the structures <code>v</code> and <code>w</code> after
evaluating this expression.  What would be printed as the values of <code>v</code>
and <code>w</code>?
</p></blockquote>

<a id="Sharing-and-identity"></a>
<h5 class="subsubheading">Sharing and identity</h5>

<p>We mentioned in <a href="3_002e1.xhtml#g_t3_002e1_002e3">3.1.3</a> the theoretical issues of “sameness” and
“change” raised by the introduction of assignment.  These issues arise in
practice when individual pairs are <a id="index-shared"></a>
<em>shared</em> among different data
objects.  For example, consider the structure formed by
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> x </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'a</span><span class="pln"> </span><span class="lit">'b</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> z1 </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> x x</span><span class="clo">))</span></pre></div>

<p>As shown in <a href="#Figure-3_002e16">Figure 3.16</a>, <code>z1</code> is a pair whose <code>car</code> and
<code>cdr</code> both point to the same pair <code>x</code>.  This sharing of <code>x</code> by
the <code>car</code> and <code>cdr</code> of <code>z1</code> is a consequence of the
straightforward way in which <code>cons</code> is implemented.  In general, using
<code>cons</code> to construct lists will result in an interlinked structure of pairs
in which many individual pairs are shared by many different structures.
</p>
<figure class="float">
<a id="Figure-3_002e16"></a>
<object style="width: 31.08ex; height: 19.69ex;" data="fig/chap3/Fig3.16b.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.16:</strong> The list <code>z1</code> formed by <code>(cons x x)</code>.</p>
</figcaption>
</figure>

<p>In contrast to <a href="#Figure-3_002e16">Figure 3.16</a>, <a href="#Figure-3_002e17">Figure 3.17</a> shows the structure created
by
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> z2 
  </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'a</span><span class="pln"> </span><span class="lit">'b</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'a</span><span class="pln"> </span><span class="lit">'b</span><span class="clo">)))</span></pre></div>

<figure class="float">
<a id="Figure-3_002e17"></a>
<object style="width: 47.57ex; height: 17.96ex;" data="fig/chap3/Fig3.17b.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.17:</strong> The list <code>z2</code> formed by <code>(cons (list 'a 'b) (list 'a 'b))</code>.</p>
</figcaption>
</figure>

<p>In this structure, the pairs in the two <code>(a b)</code> lists are distinct,
although the actual symbols are shared.<a class="footnote_link" id="DOCF147" href="#FOOT147"><sup>147</sup></a>
</p>
<p>When thought of as a list, <code>z1</code> and <code>z2</code> both represent “the same”
list, <code>((a b) a b)</code>.  In general, sharing is completely undetectable if we
operate on lists using only <code>cons</code>, <code>car</code>, and <code>cdr</code>.  However,
if we allow mutators on list structure, sharing becomes significant.  As an
example of the difference that sharing can make, consider the following
procedure, which modifies the <code>car</code> of the structure to which it is
applied:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">set-to-wow! x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">set-car! </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> x</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'wow</span><span class="clo">)</span><span class="pln">
  x</span><span class="clo">)</span></pre></div>

<p>Even though <code>z1</code> and <code>z2</code> are “the same” structure, applying
<code>set-to-wow!</code> to them yields different results.  With <code>z1</code>, altering
the <code>car</code> also changes the <code>cdr</code>, because in <code>z1</code> the <code>car</code>
and the <code>cdr</code> are the same pair.  With <code>z2</code>, the <code>car</code> and
<code>cdr</code> are distinct, so <code>set-to-wow!</code> modifies only the <code>car</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">z1
</span><i><span class="opn">((</span><span class="pln">a b</span><span class="clo">)</span><span class="pln"> a b</span><span class="clo">)</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">set-to-wow! z1</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">((</span><span class="pln">wow b</span><span class="clo">)</span><span class="pln"> wow b</span><span class="clo">)</span></i><span class="pln">

z2
</span><i><span class="opn">((</span><span class="pln">a b</span><span class="clo">)</span><span class="pln"> a b</span><span class="clo">)</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">set-to-wow! z2</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">((</span><span class="pln">wow b</span><span class="clo">)</span><span class="pln"> a b</span><span class="clo">)</span></i>
</pre></div>

<p>One way to detect sharing in list structures is to use the predicate
<code>eq?</code>, which we introduced in <a href="2_002e3.xhtml#g_t2_002e3_002e1">2.3.1</a> as a way to test whether
two symbols are equal.  More generally, <code>(eq?  x y)</code> tests whether
<code>x</code> and <code>y</code> are the same object (that is, whether <code>x</code> and
<code>y</code> are equal as pointers).  Thus, with <code>z1</code> and <code>z2</code> as defined
in <a href="#Figure-3_002e16">Figure 3.16</a> and <a href="#Figure-3_002e17">Figure 3.17</a>, <code>(eq?  (car z1) (cdr
z1))</code> is true and <code>(eq? (car z2) (cdr z2))</code> is false.
</p>
<p>As will be seen in the following sections, we can exploit sharing to greatly
extend the repertoire of data structures that can be represented by pairs.  On
the other hand, sharing can also be dangerous, since modifications made to
structures will also affect other structures that happen to share the modified
parts.  The mutation operations <code>set-car!</code> and <code>set-cdr!</code> should be
used with care; unless we have a good understanding of how our data objects are
shared, mutation can have unanticipated results.<a class="footnote_link" id="DOCF148" href="#FOOT148"><sup>148</sup></a>
</p>
<blockquote>
<p><strong><a id="Exercise-3_002e15"></a>Exercise 3.15:</strong> Draw box-and-pointer diagrams to
explain the effect of <code>set-to-wow!</code> on the structures <code>z1</code> and
<code>z2</code> above.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e16"></a>Exercise 3.16:</strong> Ben Bitdiddle decides to write a
procedure to count the number of pairs in any list structure.  “It’s easy,”
he reasons.  “The number of pairs in any structure is the number in the
<code>car</code> plus the number in the <code>cdr</code> plus one more to count the current
pair.”  So Ben writes the following procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">count-pairs x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">not </span><span class="opn">(</span><span class="pln">pair? x</span><span class="clo">))</span><span class="pln">
      </span><span class="lit">0</span><span class="pln">
      </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">count-pairs </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> x</span><span class="clo">))</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">count-pairs </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> x</span><span class="clo">))</span><span class="pln">
         </span><span class="lit">1</span><span class="clo">)))</span></pre></div>

<p>Show that this procedure is not correct.  In particular, draw box-and-pointer
diagrams representing list structures made up of exactly three pairs for which
Ben’s procedure would return 3; return 4; return 7; never return at all.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e17"></a>Exercise 3.17:</strong> Devise a correct version of the
<code>count-pairs</code> procedure of <a href="#Exercise-3_002e16">Exercise 3.16</a> that returns the number of
distinct pairs in any structure.  (Hint: Traverse the structure, maintaining an
auxiliary data structure that is used to keep track of which pairs have already
been counted.)
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e18"></a>Exercise 3.18:</strong> Write a procedure that examines a
list and determines whether it contains a cycle, that is, whether a program
that tried to find the end of the list by taking successive <code>cdr</code>s would
go into an infinite loop.  <a href="#Exercise-3_002e13">Exercise 3.13</a> constructed such lists.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e19"></a>Exercise 3.19:</strong> Redo <a href="#Exercise-3_002e18">Exercise 3.18</a> using an
algorithm that takes only a constant amount of space.  (This requires a very
clever idea.)
</p></blockquote>

<a id="Mutation-is-just-assignment"></a>
<h5 class="subsubheading">Mutation is just assignment</h5>

<p>When we introduced compound data, we observed in <a href="2_002e1.xhtml#g_t2_002e1_002e3">2.1.3</a> that pairs
can be represented purely in terms of procedures:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> x y</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">dispatch m</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'car</span><span class="clo">)</span><span class="pln"> x</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'cdr</span><span class="clo">)</span><span class="pln"> y</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Undefined 
                 operation: CONS"</span><span class="pln"> m</span><span class="clo">))))</span><span class="pln">
  dispatch</span><span class="clo">)</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> z</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">z </span><span class="lit">'car</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> z</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">z </span><span class="lit">'cdr</span><span class="clo">))</span></pre></div>

<p>The same observation is true for mutable data.  We can implement mutable data
objects as procedures using assignment and local state.  For instance, we can
extend the above pair implementation to handle <code>set-car!</code> and
<code>set-cdr!</code> in a manner analogous to the way we implemented bank accounts
using <code>make-account</code> in <a href="3_002e1.xhtml#g_t3_002e1_002e1">3.1.1</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> x y</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">set-x! v</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> x v</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">set-y! v</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> y v</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">dispatch m</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'car</span><span class="clo">)</span><span class="pln"> x</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'cdr</span><span class="clo">)</span><span class="pln"> y</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'set-car!</span><span class="clo">)</span><span class="pln"> set-x!</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'set-cdr!</span><span class="clo">)</span><span class="pln"> set-y!</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Undefined 
                 operation: CONS"</span><span class="pln"> m</span><span class="clo">))))</span><span class="pln">
  dispatch</span><span class="clo">)</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> z</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">z </span><span class="lit">'car</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> z</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">z </span><span class="lit">'cdr</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">set-car! z new-value</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">((</span><span class="pln">z </span><span class="lit">'set-car!</span><span class="clo">)</span><span class="pln"> new-value</span><span class="clo">)</span><span class="pln">
  z</span><span class="clo">)</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">set-cdr! z new-value</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">((</span><span class="pln">z </span><span class="lit">'set-cdr!</span><span class="clo">)</span><span class="pln"> new-value</span><span class="clo">)</span><span class="pln">
  z</span><span class="clo">)</span></pre></div>

<p>Assignment is all that is needed, theoretically, to account for the behavior of
mutable data.  As soon as we admit <code>set!</code> to our language, we raise all
the issues, not only of assignment, but of mutable data in general.<a class="footnote_link" id="DOCF149" href="#FOOT149"><sup>149</sup></a>
</p>
<blockquote>
<p><strong><a id="Exercise-3_002e20"></a>Exercise 3.20:</strong> Draw environment diagrams to
illustrate the evaluation of the sequence of expressions
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> x </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> z </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> x x</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">set-car! </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> z</span><span class="clo">)</span><span class="pln"> </span><span class="lit">17</span><span class="clo">)</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> x</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">17</span></i>
</pre></div>

<p>using the procedural implementation of pairs given above.  (Compare
<a href="3_002e2.xhtml#Exercise-3_002e11">Exercise 3.11</a>.)
</p></blockquote>

<a id="g_t3_002e3_002e2"></a>
<a id="Representing-Queues"></a>
<h4 class="subsection"><span class="secnum">3.3.2</span><span class="sectitle">Representing Queues</span></h4>

<p>The mutators <code>set-car!</code> and <code>set-cdr!</code> enable us to use pairs to
construct data structures that cannot be built with <code>cons</code>, <code>car</code>,
and <code>cdr</code> alone.  This section shows how to use pairs to represent a data
structure called a queue.  Section <a href="#g_t3_002e3_002e3">3.3.3</a> will show how to represent data
structures called tables.
</p>
<p>A <a id="index-queue"></a>
<em>queue</em> is a sequence in which items are inserted at one end (called
the <a id="index-rear"></a>
<em>rear</em> of the queue) and deleted from the other end (the
<a id="index-front"></a>
<em>front</em>).  <a href="#Figure-3_002e18">Figure 3.18</a> shows an initially empty queue in which
the items <code>a</code> and <code>b</code> are inserted.  Then <code>a</code> is removed,
<code>c</code> and <code>d</code> are inserted, and <code>b</code> is removed.  Because items are
always removed in the order in which they are inserted, a queue is sometimes
called a <a id="index-FIFO"></a>
<em>FIFO</em> (first in, first out) buffer.
</p>
<figure class="float">
<a id="Figure-3_002e18"></a>
<object style="width: 48.01ex; height: 23.05ex;" data="fig/chap3/Fig3.18.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.18:</strong> Queue operations.</p>
</figcaption>
</figure>

<p>In terms of data abstraction, we can regard a queue as defined by the following
set of operations:
</p>
<ul>
<li> a constructor: <code>(make-queue)</code> returns an empty queue (a queue containing
no items).

</li><li> two selectors:

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">empty-queue? ⟨</span><var><span class="pln">queue</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>tests if the queue is empty.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">front-queue ⟨</span><var><span class="pln">queue</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>returns the object at the front of the queue, signaling an error if the queue
is empty; it does not modify the queue.
</p>
</li><li> two mutators:

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">insert-queue! ⟨</span><var><span class="pln">queue</span></var><span class="pln">⟩ ⟨</span><var><span class="pln">item</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>inserts the item at the rear of the queue and returns the modified queue as its
value.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">delete-queue! ⟨</span><var><span class="pln">queue</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>removes the item at the front of the queue and returns the modified queue as
its value, signaling an error if the queue is empty before the deletion.
</p>
</li></ul>

<p>Because a queue is a sequence of items, we could certainly represent it as an
ordinary list; the front of the queue would be the <code>car</code> of the list,
inserting an item in the queue would amount to appending a new element at the
end of the list, and deleting an item from the queue would just be taking the
<code>cdr</code> of the list.  However, this representation is inefficient, because
in order to insert an item we must scan the list until we reach the end.  Since
the only method we have for scanning a list is by successive <code>cdr</code>
operations, this scanning requires <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> steps for a list of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>
items.  A simple modification to the list representation overcomes this
disadvantage by allowing the queue operations to be implemented so that they
require <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
  </mrow>
</math> steps; that is, so that the number of steps needed is
independent of the length of the queue.
</p>
<p>The difficulty with the list representation arises from the need to scan to
find the end of the list.  The reason we need to scan is that, although the
standard way of representing a list as a chain of pairs readily provides us
with a pointer to the beginning of the list, it gives us no easily accessible
pointer to the end.  The modification that avoids the drawback is to represent
the queue as a list, together with an additional pointer that indicates the
final pair in the list.  That way, when we go to insert an item, we can consult
the rear pointer and so avoid scanning the list.
</p>
<p>A queue is represented, then, as a pair of pointers, <code>front-ptr</code> and
<code>rear-ptr</code>, which indicate, respectively, the first and last pairs in an
ordinary list.  Since we would like the queue to be an identifiable object, we
can use <code>cons</code> to combine the two pointers.  Thus, the queue itself will
be the <code>cons</code> of the two pointers.  <a href="#Figure-3_002e19">Figure 3.19</a> illustrates this
representation.
</p>
<figure class="float">
<a id="Figure-3_002e19"></a>
<object style="width: 46.54ex; height: 22.45ex;" data="fig/chap3/Fig3.19b.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.19:</strong> Implementation of a queue as a list with front and rear pointers.</p>
</figcaption>
</figure>

<p>To define the queue operations we use the following procedures, which enable us
to select and to modify the front and rear pointers of a queue:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">front-ptr queue</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> queue</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">rear-ptr queue</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> queue</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">set-front-ptr! queue item</span><span class="clo">)</span><span class="pln"> 
  </span><span class="opn">(</span><span class="pln">set-car! queue item</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">set-rear-ptr! queue item</span><span class="clo">)</span><span class="pln"> 
  </span><span class="opn">(</span><span class="pln">set-cdr! queue item</span><span class="clo">))</span></pre></div>

<p>Now we can implement the actual queue operations.  We will consider a queue to
be empty if its front pointer is the empty list:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">empty-queue? queue</span><span class="clo">)</span><span class="pln"> 
  </span><span class="opn">(</span><span class="pln">null? </span><span class="opn">(</span><span class="pln">front-ptr queue</span><span class="clo">)))</span></pre></div>

<p>The <code>make-queue</code> constructor returns, as an initially empty queue, a pair
whose <code>car</code> and <code>cdr</code> are both the empty list:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-queue</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)))</span></pre></div>

<p>To select the item at the front of the queue, we return the <code>car</code> of the
pair indicated by the front pointer:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">front-queue queue</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">empty-queue? queue</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"FRONT called with an 
              empty queue"</span><span class="pln"> queue</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> </span><span class="opn">(</span><span class="pln">front-ptr queue</span><span class="clo">))))</span></pre></div>

<p>To insert an item in a queue, we follow the method whose result is indicated in
<a href="#Figure-3_002e20">Figure 3.20</a>.  We first create a new pair whose <code>car</code> is the item to
be inserted and whose <code>cdr</code> is the empty list.  If the queue was initially
empty, we set the front and rear pointers of the queue to this new pair.
Otherwise, we modify the final pair in the queue to point to the new pair, and
also set the rear pointer to the new pair.
</p>
<figure class="float">
<a id="Figure-3_002e20"></a>
<object style="width: 55.09ex; height: 22.45ex;" data="fig/chap3/Fig3.20c.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.20:</strong> Result of using <code>(insert-queue! q 'd)</code> on the queue of <a href="#Figure-3_002e19">Figure 3.19</a>.</p>
</figcaption>
</figure>

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">insert-queue! queue item</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">new-pair </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> item </span><span class="lit">'</span><span class="opn">(</span><span class="clo">))))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">empty-queue? queue</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">set-front-ptr! queue new-pair</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">set-rear-ptr! queue new-pair</span><span class="clo">)</span><span class="pln">
           queue</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="pln">set-cdr! </span><span class="opn">(</span><span class="pln">rear-ptr queue</span><span class="clo">)</span><span class="pln"> 
                          new-pair</span><span class="clo">)</span><span class="pln">
                </span><span class="opn">(</span><span class="pln">set-rear-ptr! queue new-pair</span><span class="clo">)</span><span class="pln">
                queue</span><span class="clo">))))</span></pre></div>

<p>To delete the item at the front of the queue, we merely modify the front
pointer so that it now points at the second item in the queue, which can be
found by following the <code>cdr</code> pointer of the first item (see 
<a href="#Figure-3_002e21">Figure 3.21</a>):<a class="footnote_link" id="DOCF150" href="#FOOT150"><sup>150</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">delete-queue! queue</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">empty-queue? queue</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"DELETE! called with 
                 an empty queue"</span><span class="pln"> queue</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="pln">set-front-ptr! 
               queue 
               </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> </span><span class="opn">(</span><span class="pln">front-ptr queue</span><span class="clo">)))</span><span class="pln">
              queue</span><span class="clo">)))</span></pre></div>

<figure class="float">
<a id="Figure-3_002e21"></a>
<object style="width: 55.09ex; height: 22.45ex;" data="fig/chap3/Fig3.21c.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.21:</strong> Result of using <code>(delete-queue!  q)</code> on the queue of <a href="#Figure-3_002e20">Figure 3.20</a>.</p>
</figcaption>
</figure>

<blockquote>
<p><strong><a id="Exercise-3_002e21"></a>Exercise 3.21:</strong> Ben Bitdiddle decides to test the
queue implementation described above.  He types in the procedures to the Lisp
interpreter and proceeds to try them out:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> q1 </span><span class="opn">(</span><span class="pln">make-queue</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">insert-queue! q1 </span><span class="lit">'a</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">((</span><span class="pln">a</span><span class="clo">)</span><span class="pln"> a</span><span class="clo">)</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">insert-queue! q1 </span><span class="lit">'b</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">((</span><span class="pln">a b</span><span class="clo">)</span><span class="pln"> b</span><span class="clo">)</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">delete-queue! q1</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">((</span><span class="pln">b</span><span class="clo">)</span><span class="pln"> b</span><span class="clo">)</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">delete-queue! q1</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">((</span><span class="clo">)</span><span class="pln"> b</span><span class="clo">)</span></i>
</pre></div>

<p>“It’s all wrong!” he complains.  “The interpreter’s response shows that the
last item is inserted into the queue twice.  And when I delete both items, the
second <code>b</code> is still there, so the queue isn’t empty, even though it’s
supposed to be.”  Eva Lu Ator suggests that Ben has misunderstood what is
happening.  “It’s not that the items are going into the queue twice,” she
explains.  “It’s just that the standard Lisp printer doesn’t know how to make
sense of the queue representation.  If you want to see the queue printed
correctly, you’ll have to define your own print procedure for queues.” Explain
what Eva Lu is talking about.  In particular, show why Ben’s examples produce
the printed results that they do.  Define a procedure <code>print-queue</code> that
takes a queue as input and prints the sequence of items in the queue.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e22"></a>Exercise 3.22:</strong> Instead of representing a queue
as a pair of pointers, we can build a queue as a procedure with local state.
The local state will consist of pointers to the beginning and the end of an
ordinary list.  Thus, the <code>make-queue</code> procedure will have the form
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-queue</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">front-ptr </span><span class="roman"><span class="pun">…</span></span><span class="pln"> </span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">rear-ptr </span><span class="roman"><span class="pun">…</span></span><span class="pln"> </span><span class="clo">))</span><span class="pln">
    ⟨</span><var><span class="pln">definitions of internal procedures</span></var><span class="pln">⟩
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">dispatch m</span><span class="clo">)</span><span class="pln"> </span><span class="roman"><span class="pun">…</span></span><span class="clo">)</span><span class="pln">
    dispatch</span><span class="clo">))</span></pre></div>

<p>Complete the definition of <code>make-queue</code> and provide implementations of the
queue operations using this representation.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e23"></a>Exercise 3.23:</strong> A <a id="index-deque"></a>
<em>deque</em> (“double-ended
                                                                 queue”) is a sequence in which items can be inserted and deleted at either the
front or the rear.  Operations on deques are the constructor <code>make-deque</code>,
the predicate <code>empty-deque?</code>, selectors <code>front-deque</code> and
<code>rear-deque</code>, and mutators <code>front-insert-deque!</code>,
<code>rear-insert-deque!</code>, <code>front-delete-deque!</code>, 
<code>rear-delete-deque!</code>.  Show how to represent deques using pairs, and give
implementations of the operations.<a class="footnote_link" id="DOCF151" href="#FOOT151"><sup>151</sup></a>  
All operations should be accomplished in <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
  </mrow>
</math> steps.
</p></blockquote>

<a id="g_t3_002e3_002e3"></a>
<a id="Representing-Tables"></a>
<h4 class="subsection"><span class="secnum">3.3.3</span><span class="sectitle">Representing Tables</span></h4>

<p>When we studied various ways of representing sets in <a href="Chapter-2.xhtml#Chapter-2">Chapter 2</a>, we
mentioned in <a href="2_002e3.xhtml#g_t2_002e3_002e3">2.3.3</a> the task of maintaining a table of records
indexed by identifying keys.  In the implementation of data-directed
programming in <a href="2_002e4.xhtml#g_t2_002e4_002e3">2.4.3</a>, we made extensive use of two-dimensional
tables, in which information is stored and retrieved using two keys.  Here we
see how to build tables as mutable list structures.
</p>
<p>We first consider a one-dimensional table, in which each value is stored under
a single key.  We implement the table as a list of records, each of which is
implemented as a pair consisting of a key and the associated value. The records
are glued together to form a list by pairs whose <code>car</code>s point to
successive records.  These gluing pairs are called the <a id="index-backbone"></a>
<em>backbone</em> of
the table.  In order to have a place that we can change when we add a new
record to the table, we build the table as a <a id="index-headed-list"></a>
<em>headed list</em>.  A headed
list has a special backbone pair at the beginning, which holds a dummy
“record”—in this case the arbitrarily chosen symbol <code>*table*</code>.
<a href="#Figure-3_002e22">Figure 3.22</a> shows the box-and-pointer diagram for the table
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">a</span><span class="pun">:</span><span class="pln">  </span><span class="lit">1</span><span class="pln">
b</span><span class="pun">:</span><span class="pln">  </span><span class="lit">2</span><span class="pln">
c</span><span class="pun">:</span><span class="pln">  </span><span class="lit">3</span></pre></div>

<figure class="float">
<a id="Figure-3_002e22"></a>
<object style="width: 53.27ex; height: 27.11ex;" data="fig/chap3/Fig3.22c.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.22:</strong> A table represented as a headed list.</p>
</figcaption>
</figure>

<p>To extract information from a table we use the <code>lookup</code> procedure, which
takes a key as argument and returns the associated value (or false if there is
no value stored under that key).  <code>Lookup</code> is defined in terms of the
<code>assoc</code> operation, which expects a key and a list of records as arguments.
Note that <code>assoc</code> never sees the dummy record.  <code>Assoc</code> returns the
record that has the given key as its <code>car</code>.<a class="footnote_link" id="DOCF152" href="#FOOT152"><sup>152</sup></a>  <code>Lookup</code> then checks to see that the resulting record
returned by <code>assoc</code> is not false, and returns the value (the <code>cdr</code>)
of the record.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">lookup key table</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">record </span><span class="opn">(</span><span class="pln">assoc key </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> table</span><span class="clo">))))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> record
        </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> record</span><span class="clo">)</span><span class="pln">
        false</span><span class="clo">)))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">assoc key records</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">null? records</span><span class="clo">)</span><span class="pln"> false</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">equal</span><span class="pun">?</span><span class="pln"> key </span><span class="opn">(</span><span class="kwd">caar</span><span class="pln"> records</span><span class="clo">))</span><span class="pln"> 
         </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> records</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="pln">assoc key </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> records</span><span class="clo">)))))</span></pre></div>

<p>To insert a value in a table under a specified key, we first use <code>assoc</code>
to see if there is already a record in the table with this key.  If not, we
form a new record by <code>cons</code>ing the key with the value, and insert this at
the head of the table’s list of records, after the dummy record.  If there
already is a record with this key, we set the <code>cdr</code> of this record to the
designated new value.  The header of the table provides us with a fixed
location to modify in order to insert the new record.<a class="footnote_link" id="DOCF153" href="#FOOT153"><sup>153</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">insert! key value table</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">record </span><span class="opn">(</span><span class="pln">assoc key </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> table</span><span class="clo">))))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> record
        </span><span class="opn">(</span><span class="pln">set-cdr! record value</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">set-cdr! table
                  </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> key value</span><span class="clo">)</span><span class="pln"> 
                        </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> table</span><span class="clo">)))))</span><span class="pln">
  </span><span class="lit">'ok</span><span class="clo">)</span></pre></div>

<p>To construct a new table, we simply create a list containing the symbol
<code>*table*</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-table</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'</span><span class="pun">*</span><span class="pln">table</span><span class="pun">*</span><span class="clo">))</span></pre></div>

<a id="Two_002ddimensional-tables"></a>
<h5 class="subsubheading">Two-dimensional tables</h5>

<p>In a two-dimensional table, each value is indexed by two keys.  We can
construct such a table as a one-dimensional table in which each key identifies
a subtable.  <a href="#Figure-3_002e23">Figure 3.23</a> shows the box-and-pointer diagram for the table
</p>
<div class="example">
<pre class="example">math:  +: 43    letters:  a: 97
       -: 45              b: 98
       *: 42
</pre></div>

<p>which has two subtables.  (The subtables don’t need a special header symbol,
since the key that identifies the subtable serves this purpose.)
</p>
<figure class="float">
<a id="Figure-3_002e23"></a>
<object style="width: 57.42ex; height: 55.95ex;" data="fig/chap3/Fig3.23b.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.23:</strong> A two-dimensional table.</p>
</figcaption>
</figure>

<p>When we look up an item, we use the first key to identify the correct subtable.
Then we use the second key to identify the record within the subtable.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">lookup key-1 key-2 table</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">subtable </span><span class="opn">(</span><span class="pln">assoc key-1 </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> table</span><span class="clo">))))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> subtable
        </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">record 
               </span><span class="opn">(</span><span class="pln">assoc key-2 </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> subtable</span><span class="clo">))))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> record </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> record</span><span class="clo">)</span><span class="pln"> false</span><span class="clo">))</span><span class="pln">
        false</span><span class="clo">)))</span></pre></div>

<p>To insert a new item under a pair of keys, we use <code>assoc</code> to see if there
is a subtable stored under the first key.  If not, we build a new subtable
containing the single record (<code>key-2</code>, <code>value</code>) and insert it into
the table under the first key.  If a subtable already exists for the first key,
we insert the new record into this subtable, using the insertion method for
one-dimensional tables described above:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">insert! key-1 key-2 value table</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">subtable </span><span class="opn">(</span><span class="pln">assoc key-1 </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> table</span><span class="clo">))))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> subtable
        </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">record 
               </span><span class="opn">(</span><span class="pln">assoc key-2 </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> subtable</span><span class="clo">))))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> record
              </span><span class="opn">(</span><span class="pln">set-cdr! record value</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">set-cdr! 
               subtable
               </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> key-2 value</span><span class="clo">)</span><span class="pln">
                     </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> subtable</span><span class="clo">)))))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">set-cdr! 
         table
         </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list key-1 </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> key-2 value</span><span class="clo">))</span><span class="pln">
               </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> table</span><span class="clo">)))))</span><span class="pln">
  </span><span class="lit">'ok</span><span class="clo">)</span></pre></div>

<a id="Creating-local-tables"></a>
<h5 class="subsubheading">Creating local tables</h5>

<p>The <code>lookup</code> and <code>insert!</code> operations defined above take the table as
an argument.  This enables us to use programs that access more than one table.
Another way to deal with multiple tables is to have separate <code>lookup</code> and
<code>insert!</code> procedures for each table.  We can do this by representing a
table procedurally, as an object that maintains an internal table as part of
its local state.  When sent an appropriate message, this “table object”
supplies the procedure with which to operate on the internal table.  Here is a
generator for two-dimensional tables represented in this fashion:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-table</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">local-table </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'</span><span class="pun">*</span><span class="pln">table</span><span class="pun">*</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">lookup key-1 key-2</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">subtable 
             </span><span class="opn">(</span><span class="pln">assoc key-1 </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> local-table</span><span class="clo">))))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> subtable
            </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">record 
                   </span><span class="opn">(</span><span class="pln">assoc key-2 
                          </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> subtable</span><span class="clo">))))</span><span class="pln">
              </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> record </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> record</span><span class="clo">)</span><span class="pln"> false</span><span class="clo">))</span><span class="pln">
            false</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">insert! key-1 key-2 value</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">subtable 
             </span><span class="opn">(</span><span class="pln">assoc key-1 </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> local-table</span><span class="clo">))))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> subtable
            </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">record 
                   </span><span class="opn">(</span><span class="pln">assoc key-2 
                          </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> subtable</span><span class="clo">))))</span><span class="pln">
              </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> record
                  </span><span class="opn">(</span><span class="pln">set-cdr! record value</span><span class="clo">)</span><span class="pln">
                  </span><span class="opn">(</span><span class="pln">set-cdr! 
                   subtable
                   </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> key-2 value</span><span class="clo">)</span><span class="pln">
                         </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> subtable</span><span class="clo">)))))</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">set-cdr! 
             local-table
             </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list key-1
                         </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> key-2 value</span><span class="clo">))</span><span class="pln">
                   </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> local-table</span><span class="clo">)))))</span><span class="pln">
      </span><span class="lit">'ok</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">dispatch m</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'lookup-proc</span><span class="clo">)</span><span class="pln"> lookup</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'insert-proc!</span><span class="clo">)</span><span class="pln"> insert!</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unknown operation: 
                          TABLE"</span><span class="pln"> m</span><span class="clo">))))</span><span class="pln">
    dispatch</span><span class="clo">))</span></pre></div>

<p>Using <code>make-table</code>, we could implement the <code>get</code> and <code>put</code>
operations used in <a href="2_002e4.xhtml#g_t2_002e4_002e3">2.4.3</a> for data-directed programming, as
follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> operation-table </span><span class="opn">(</span><span class="pln">make-table</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> get </span><span class="opn">(</span><span class="pln">operation-table </span><span class="lit">'lookup-proc</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> put </span><span class="opn">(</span><span class="pln">operation-table </span><span class="lit">'insert-proc!</span><span class="clo">))</span></pre></div>

<p><code>Get</code> takes as arguments two keys, and <code>put</code> takes as arguments two
keys and a value.  Both operations access the same local table, which is
encapsulated within the object created by the call to <code>make-table</code>.
</p>
<blockquote>
<p><strong><a id="Exercise-3_002e24"></a>Exercise 3.24:</strong> In the table implementations
above, the keys are tested for equality using <code>equal?</code> (called by
<code>assoc</code>).  This is not always the appropriate test.  For instance, we
might have a table with numeric keys in which we don’t need an exact match to
the number we’re looking up, but only a number within some tolerance of it.
Design a table constructor <code>make-table</code> that takes as an argument a
<code>same-key?</code> procedure that will be used to test “equality” of keys.
<code>Make-table</code> should return a <code>dispatch</code> procedure that can be used to
access appropriate <code>lookup</code> and <code>insert!</code> procedures for a local
table.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e25"></a>Exercise 3.25:</strong> Generalizing one- and
two-dimensional tables, show how to implement a table in which values are
stored under an arbitrary number of keys and different values may be stored
under different numbers of keys.  The <code>lookup</code> and <code>insert!</code>
procedures should take as input a list of keys used to access the table.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e26"></a>Exercise 3.26:</strong> To search a table as implemented
above, one needs to scan through the list of records.  This is basically the
unordered list representation of <a href="2_002e3.xhtml#g_t2_002e3_002e3">2.3.3</a>.  For large tables, it may
be more efficient to structure the table in a different manner.  Describe a
table implementation where the (key, value) records are organized using a
binary tree, assuming that keys can be ordered in some way (e.g., numerically
or alphabetically).  (Compare <a href="2_002e3.xhtml#Exercise-2_002e66">Exercise 2.66</a> of <a href="Chapter-2.xhtml#Chapter-2">Chapter 2</a>.)
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e27"></a>Exercise 3.27:</strong> <a id="index-Memoization"></a>
<em>Memoization</em> (also
called <a id="index-tabulation-1"></a>
<em>tabulation</em>) is a technique that enables a procedure to record,
in a local table, values that have previously been computed.  This technique
can make a vast difference in the performance of a program.  A memoized
procedure maintains a table in which values of previous calls are stored using
as keys the arguments that produced the values.  When the memoized procedure is
asked to compute a value, it first checks the table to see if the value is
already there and, if so, just returns that value.  Otherwise, it computes the
new value in the ordinary way and stores this in the table.  As an example of
memoization, recall from <a href="1_002e2.xhtml#g_t1_002e2_002e2">1.2.2</a> the exponential process for
computing Fibonacci numbers:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fib n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fib </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))</span><span class="pln">
                 </span><span class="opn">(</span><span class="pln">fib </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">2</span><span class="clo">))))))</span></pre></div>

<p>The memoized version of the same procedure is
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> memo-fib
  </span><span class="opn">(</span><span class="pln">memoize 
   </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">n</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> 
            </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">memo-fib </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">memo-fib </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">2</span><span class="clo">))))))))</span></pre></div>

<p>where the memoizer is defined as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">memoize f</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">table </span><span class="opn">(</span><span class="pln">make-table</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">previously-computed-result 
             </span><span class="opn">(</span><span class="pln">lookup x table</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">or</span><span class="pln"> previously-computed-result
            </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">result </span><span class="opn">(</span><span class="pln">f x</span><span class="clo">)))</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">insert! x result table</span><span class="clo">)</span><span class="pln">
              result</span><span class="clo">))))))</span></pre></div>

<p>Draw an environment diagram to analyze the computation of <code>(memo-fib 3)</code>.
Explain why <code>memo-fib</code> computes the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>n</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mtext>th</mtext>
    </mrow>
  </msup>
</math> Fibonacci number in a number
of steps proportional to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.  Would the scheme still work if we had simply
defined <code>memo-fib</code> to be <code>(memoize fib)</code>?
</p></blockquote>

<a id="g_t3_002e3_002e4"></a>
<a id="A-Simulator-for-Digital-Circuits"></a>
<h4 class="subsection"><span class="secnum">3.3.4</span><span class="sectitle">A Simulator for Digital Circuits</span></h4>

<p>Designing complex digital systems, such as computers, is an important
engineering activity.  Digital systems are constructed by interconnecting
simple elements.  Although the behavior of these individual elements is simple,
networks of them can have very complex behavior.  Computer simulation of
proposed circuit designs is an important tool used by digital systems
engineers.  In this section we design a system for performing digital logic
simulations.  This system typifies a kind of program called an
<a id="index-event_002ddriven-simulation"></a>
<em>event-driven simulation</em>, in which actions (“events”) trigger
further events that happen at a later time, which in turn trigger more events,
and so on.
</p>
<p>Our computational model of a circuit will be composed of objects that
correspond to the elementary components from which the circuit is constructed.
There are <a id="index-wires"></a>
<em>wires</em>, which carry <a id="index-digital-signals"></a>
<em>digital signals</em>.  A digital
signal may at any moment have only one of two possible values, 0 and 1.  There
are also various types of digital <a id="index-function-boxes"></a>
<em>function boxes</em>, which connect wires
carrying input signals to other output wires.  Such boxes produce output
signals computed from their input signals.  The output signal is delayed by a
time that depends on the type of the function box.  For example, an
<a id="index-inverter"></a>
<em>inverter</em> is a primitive function box that inverts its input.  If the
input signal to an inverter changes to 0, then one inverter-delay later the
inverter will change its output signal to 1.  If the input signal to an
inverter changes to 1, then one inverter-delay later the inverter will change
its output signal to 0.  We draw an inverter symbolically as in <a href="#Figure-3_002e24">Figure 3.24</a>.  
An <a id="index-and_002dgate"></a>
<em>and-gate</em>, also shown in figure 3.24, is a primitive
function box with two inputs and one output.  It drives its output signal to a
value that is the <a id="index-logical-and"></a>
<em>logical and</em> of the inputs.  That is, if both of its
input signals become 1, then one and-gate-delay time later the and-gate will
force its output signal to be 1; otherwise the output will be 0.  An
<a id="index-or_002dgate"></a>
<em>or-gate</em> is a similar two-input primitive function box that drives its
output signal to a value that is the <a id="index-logical-or"></a>
<em>logical or</em> of the inputs.  That
is, the output will become 1 if at least one of the input signals is 1;
otherwise the output will become 0.
</p>
<figure class="float">
<a id="Figure-3_002e24"></a>
<object style="width: 49.30ex; height: 11.14ex;" data="fig/chap3/Fig3.24a.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.24:</strong> Primitive functions in the digital logic simulator.</p>
</figcaption>
</figure>

<p>We can connect primitive functions together to construct more complex
functions.  To accomplish this we wire the outputs of some function boxes to
the inputs of other function boxes.  For example, the <a id="index-half_002dadder"></a>
<em>half-adder</em>
circuit shown in <a href="#Figure-3_002e25">Figure 3.25</a> consists of an or-gate, two and-gates, and
an inverter.  It takes two input signals, A and B, and has two output signals,
S and C.  S will become 1 whenever precisely one of A and B is 1, and C will
become 1 whenever A and B are both 1.  We can see from the figure that, because
of the delays involved, the outputs may be generated at different times.  Many
of the difficulties in the design of digital circuits arise from this fact.
</p>
<figure class="float">
<a id="Figure-3_002e25"></a>
<object style="width: 48.52ex; height: 19.17ex;" data="fig/chap3/Fig3.25c.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.25:</strong> A half-adder circuit.</p>
</figcaption>
</figure>

<p>We will now build a program for modeling the digital logic circuits we wish to
study.  The program will construct computational objects modeling the wires,
which will “hold” the signals.  Function boxes will be modeled by procedures
that enforce the correct relationships among the signals.
</p>
<p>One basic element of our simulation will be a procedure <code>make-wire</code>, which
constructs wires.  For example, we can construct six wires as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> a </span><span class="opn">(</span><span class="pln">make-wire</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> b </span><span class="opn">(</span><span class="pln">make-wire</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> c </span><span class="opn">(</span><span class="pln">make-wire</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> d </span><span class="opn">(</span><span class="pln">make-wire</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> e </span><span class="opn">(</span><span class="pln">make-wire</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> s </span><span class="opn">(</span><span class="pln">make-wire</span><span class="clo">))</span></pre></div>

<p>We attach a function box to a set of wires by calling a procedure that
constructs that kind of box.  The arguments to the constructor procedure are
the wires to be attached to the box.  For example, given that we can construct
and-gates, or-gates, and inverters, we can wire together the half-adder shown
in <a href="#Figure-3_002e25">Figure 3.25</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">or-gate a b d</span><span class="clo">)</span><span class="pln">
</span><i><span class="pln">ok</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">and-gate a b c</span><span class="clo">)</span><span class="pln">
</span><i><span class="pln">ok</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">inverter c e</span><span class="clo">)</span><span class="pln">
</span><i><span class="pln">ok</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">and-gate d e s</span><span class="clo">)</span><span class="pln">
</span><i><span class="pln">ok</span></i>
</pre></div>

<p>Better yet, we can explicitly name this operation by defining a procedure
<code>half-adder</code> that constructs this circuit, given the four external wires
to be attached to the half-adder:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">half-adder a b s c</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">d </span><span class="opn">(</span><span class="pln">make-wire</span><span class="clo">))</span><span class="pln"> </span><span class="opn">(</span><span class="pln">e </span><span class="opn">(</span><span class="pln">make-wire</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">or-gate a b d</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">and-gate a b c</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">inverter c e</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">and-gate d e s</span><span class="clo">)</span><span class="pln">
    </span><span class="lit">'ok</span><span class="clo">))</span></pre></div>

<p>The advantage of making this definition is that we can use <code>half-adder</code>
itself as a building block in creating more complex circuits.  <a href="#Figure-3_002e26">Figure 3.26</a>, 
for example, shows a <a id="index-full_002dadder"></a>
<em>full-adder</em> composed of two half-adders
and an or-gate.<a class="footnote_link" id="DOCF154" href="#FOOT154"><sup>154</sup></a> We can construct a full-adder as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">full-adder a b c-in sum c-out</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">c1 </span><span class="opn">(</span><span class="pln">make-wire</span><span class="clo">))</span><span class="pln"> 
        </span><span class="opn">(</span><span class="pln">c2 </span><span class="opn">(</span><span class="pln">make-wire</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">s  </span><span class="opn">(</span><span class="pln">make-wire</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">half-adder b c-in s c1</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">half-adder a s sum c2</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">or-gate c1 c2 c-out</span><span class="clo">)</span><span class="pln">
    </span><span class="lit">'ok</span><span class="clo">))</span></pre></div>

<figure class="float">
<a id="Figure-3_002e26"></a>
<object style="width: 51.29ex; height: 19.17ex;" data="fig/chap3/Fig3.26.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.26:</strong> A full-adder circuit.</p>
</figcaption>
</figure>

<p>Having defined <code>full-adder</code> as a procedure, we can now use it as a
building block for creating still more complex circuits.  (For example, see
<a href="#Exercise-3_002e30">Exercise 3.30</a>.)
</p>
<p>In essence, our simulator provides us with the tools to construct a language of
circuits.  If we adopt the general perspective on languages with which we
approached the study of Lisp in <a href="1_002e1.xhtml#g_t1_002e1">1.1</a>, we can say that the
primitive function boxes form the primitive elements of the language, that
wiring boxes together provides a means of combination, and that specifying
wiring patterns as procedures serves as a means of abstraction.
</p>
<a id="Primitive-function-boxes"></a>
<h5 class="subsubheading">Primitive function boxes</h5>

<p>The primitive function boxes implement the “forces” by which a change in the
signal on one wire influences the signals on other wires.  To build function
boxes, we use the following operations on wires:
</p>
<ul>
<li> <code>(get-signal ⟨<var>wire</var>⟩)</code>

<p>returns the current value of the signal on the wire.
</p>
</li><li> <code>(set-signal! ⟨<var>wire</var>⟩ ⟨<var>new value</var>⟩)</code>

<p>changes the value of the signal on the wire to the new value.
</p>
</li><li> <code>(add-action! ⟨<var>wire</var>⟩ ⟨<var>procedure of no arguments</var>⟩)</code>

<p>asserts that the designated procedure should be run whenever the signal on the
wire changes value.  Such procedures are the vehicles by which changes in the
signal value on the wire are communicated to other wires.
</p>
</li></ul>

<p>In addition, we will make use of a procedure <code>after-delay</code> that takes a
time delay and a procedure to be run and executes the given procedure after the
given delay.
</p>
<p>Using these procedures, we can define the primitive digital logic functions.
To connect an input to an output through an inverter, we use <code>add-action!</code>
to associate with the input wire a procedure that will be run whenever the
signal on the input wire changes value.  The procedure computes the
<code>logical-not</code> of the input signal, and then, after one
<code>inverter-delay</code>, sets the output signal to be this new value:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">inverter input output</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">invert-input</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">new-value 
           </span><span class="opn">(</span><span class="pln">logical-not </span><span class="opn">(</span><span class="pln">get-signal input</span><span class="clo">))))</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">after-delay 
       inverter-delay
       </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">set-signal! output new-value</span><span class="clo">)))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">add-action! input invert-input</span><span class="clo">)</span><span class="pln">
  </span><span class="lit">'ok</span><span class="clo">)</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">logical-not s</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> s </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> s </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Invalid signal"</span><span class="pln"> s</span><span class="clo">))))</span></pre></div>

<p>An and-gate is a little more complex.  The action procedure must be run if
either of the inputs to the gate changes.  It computes the <code>logical-and</code>
(using a procedure analogous to <code>logical-not</code>) of the values of the
signals on the input wires and sets up a change to the new value to occur on
the output wire after one <code>and-gate-delay</code>.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">and-gate a1 a2 output</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">and-action-procedure</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">new-value
           </span><span class="opn">(</span><span class="pln">logical-and </span><span class="opn">(</span><span class="pln">get-signal a1</span><span class="clo">)</span><span class="pln"> 
                        </span><span class="opn">(</span><span class="pln">get-signal a2</span><span class="clo">))))</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">after-delay 
       and-gate-delay
       </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">set-signal! output new-value</span><span class="clo">)))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">add-action! a1 and-action-procedure</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">add-action! a2 and-action-procedure</span><span class="clo">)</span><span class="pln">
  </span><span class="lit">'ok</span><span class="clo">)</span></pre></div>

<blockquote>
<p><strong><a id="Exercise-3_002e28"></a>Exercise 3.28:</strong> Define an or-gate as a primitive
function box.  Your <code>or-gate</code> constructor should be similar to
<code>and-gate</code>.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e29"></a>Exercise 3.29:</strong> Another way to construct an
or-gate is as a compound digital logic device, built from and-gates and
inverters.  Define a procedure <code>or-gate</code> that accomplishes this.  What is
the delay time of the or-gate in terms of <code>and-gate-delay</code> and
<code>inverter-delay</code>?
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e30"></a>Exercise 3.30:</strong> <a href="#Figure-3_002e27">Figure 3.27</a> shows a
<a id="index-ripple_002dcarry-adder"></a>
<em>ripple-carry adder</em> formed by stringing together <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> full-adders.
This is the simplest form of parallel adder for adding two <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>-bit binary
numbers.  The inputs <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>A</mi>
    <mn>1</mn>
  </msub>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>A</mi>
    <mn>2</mn>
  </msub>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>A</mi>
    <mn>3</mn>
  </msub>
</math>, …, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>A</mi>
    <mi>n</mi>
  </msub>
</math> and 
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>B</mi>
    <mn>1</mn>
  </msub>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>B</mi>
    <mn>2</mn>
  </msub>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>B</mi>
    <mn>3</mn>
  </msub>
</math>,
…, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>B</mi>
    <mi>n</mi>
  </msub>
</math> are the two binary numbers to be added (each <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>A</mi>
    <mi>k</mi>
  </msub>
</math> and
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>B</mi>
    <mi>k</mi>
  </msub>
</math> is a 0 or a 1).  The circuit generates <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>S</mi>
    <mn>1</mn>
  </msub>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>S</mi>
    <mn>2</mn>
  </msub>
</math>, 
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>S</mi>
    <mn>3</mn>
  </msub>
</math>, …, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>S</mi>
    <mi>n</mi>
  </msub>
</math>,
the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> bits of the sum, and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>C</mi>
</math>, the carry from the addition.  Write a
procedure <code>ripple-carry-adder</code> that generates this circuit.  The procedure
should take as arguments three lists of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> wires each—the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>A</mi>
    <mi>k</mi>
  </msub>
</math>, the
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>B</mi>
    <mi>k</mi>
  </msub>
</math>, and the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>S</mi>
    <mi>k</mi>
  </msub>
</math>—and also another wire <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>C</mi>
</math>.  The major drawback of the
ripple-carry adder is the need to wait for the carry signals to propagate.
What is the delay needed to obtain the complete output from an <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>-bit
ripple-carry adder, expressed in terms of the delays for and-gates, or-gates,
and inverters?
</p></blockquote>

<figure class="float">
<a id="Figure-3_002e27"></a>
<object style="width: 50.16ex; height: 15.54ex;" data="fig/chap3/Fig3.27b.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.27:</strong> A ripple-carry adder for <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>-bit numbers.</p>
</figcaption>
</figure>

<a id="Representing-wires"></a>
<h5 class="subsubheading">Representing wires</h5>

<p>A wire in our simulation will be a computational object with two local state
variables: a <code>signal-value</code> (initially taken to be 0) and a collection of
<code>action-procedures</code> to be run when the signal changes value.  We implement
the wire, using message-passing style, as a collection of local procedures
together with a <code>dispatch</code> procedure that selects the appropriate local
operation, just as we did with the simple bank-account object in 
<a href="3_002e1.xhtml#g_t3_002e1_002e1">3.1.1</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-wire</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">signal-value </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> 
        </span><span class="opn">(</span><span class="pln">action-procedures </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">set-my-signal! new-value</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">not </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> signal-value new-value</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">begin</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> signal-value new-value</span><span class="clo">)</span><span class="pln">
                 </span><span class="opn">(</span><span class="pln">call-each 
                  action-procedures</span><span class="clo">))</span><span class="pln">
          </span><span class="lit">'done</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">accept-action-procedure! proc</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> action-procedures 
            </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> proc action-procedures</span><span class="clo">))</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">proc</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">dispatch m</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'get-signal</span><span class="clo">)</span><span class="pln"> 
             signal-value</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'set-signal!</span><span class="clo">)</span><span class="pln"> 
             set-my-signal!</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'add-action!</span><span class="clo">)</span><span class="pln"> 
             accept-action-procedure!</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unknown operation: 
                          WIRE"</span><span class="pln"> m</span><span class="clo">))))</span><span class="pln">
    dispatch</span><span class="clo">))</span></pre></div>

<p>The local procedure <code>set-my-signal!</code> tests whether the new signal value
changes the signal on the wire.  If so, it runs each of the action procedures,
using the following procedure <code>call-each</code>, which calls each of the items
in a list of no-argument procedures:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">call-each procedures</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? procedures</span><span class="clo">)</span><span class="pln">
      </span><span class="lit">'done</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">begin</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">car</span><span class="pln"> procedures</span><span class="clo">))</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">call-each </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> procedures</span><span class="clo">)))))</span></pre></div>

<p>The local procedure <code>accept-action-procedure!</code> adds the given procedure to
the list of procedures to be run, and then runs the new procedure once.  (See
<a href="#Exercise-3_002e31">Exercise 3.31</a>.)
</p>
<p>With the local <code>dispatch</code> procedure set up as specified, we can provide
the following procedures to access the local operations on
wires:<a class="footnote_link" id="DOCF155" href="#FOOT155"><sup>155</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">get-signal wire</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">wire </span><span class="lit">'get-signal</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">set-signal! wire new-value</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">((</span><span class="pln">wire </span><span class="lit">'set-signal!</span><span class="clo">)</span><span class="pln"> new-value</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">add-action! wire action-procedure</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">((</span><span class="pln">wire </span><span class="lit">'add-action!</span><span class="clo">)</span><span class="pln"> action-procedure</span><span class="clo">))</span></pre></div>

<p>Wires, which have time-varying signals and may be incrementally attached to
devices, are typical of mutable objects.  We have modeled them as procedures
with local state variables that are modified by assignment.  When a new wire is
created, a new set of state variables is allocated (by the <code>let</code>
expression in <code>make-wire</code>) and a new <code>dispatch</code> procedure is
constructed and returned, capturing the environment with the new state
variables.
</p>
<p>The wires are shared among the various devices that have been connected to
them.  Thus, a change made by an interaction with one device will affect all
the other devices attached to the wire.  The wire communicates the change to
its neighbors by calling the action procedures provided to it when the
connections were established.
</p>
<a id="The-agenda"></a>
<h5 class="subsubheading">The agenda</h5>

<p>The only thing needed to complete the simulator is <code>after-delay</code>.  The
idea here is that we maintain a data structure, called an <a id="index-agenda"></a>
<em>agenda</em>,
that contains a schedule of things to do.  The following operations are defined
for agendas:
</p>
<ul>
<li> <code>(make-agenda)</code> returns a new empty agenda.

</li><li> <code>(empty-agenda? ⟨<var>agenda</var>⟩)</code> is true if the specified agenda is
empty.

</li><li> <code>(first-agenda-item ⟨<var>agenda</var>⟩)</code> returns the first item on the
agenda.

</li><li> <code>(remove-first-agenda-item! ⟨<var>agenda</var>⟩)</code> modifies the agenda by
removing the first item.

</li><li> <code>(add-to-agenda! ⟨<var>time</var>⟩ ⟨<var>action</var>⟩ ⟨<var>agenda</var>⟩)</code> 
modifies the agenda by adding the given action procedure to be run at the 
specified time.

</li><li> <code>(current-time ⟨<var>agenda</var>⟩)</code> returns the current simulation time.

</li></ul>

<p>The particular agenda that we use is denoted by <code>the-agenda</code>.  The
procedure <code>after-delay</code> adds new elements to <code>the-agenda</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">after-delay </span><span class="kwd">delay</span><span class="pln"> action</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">add-to-agenda! 
   </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="kwd">delay</span><span class="pln"> </span><span class="opn">(</span><span class="pln">current-time the-agenda</span><span class="clo">))</span><span class="pln">
   action
   the-agenda</span><span class="clo">))</span></pre></div>

<p>The simulation is driven by the procedure <code>propagate</code>, which operates on
<code>the-agenda</code>, executing each procedure on the agenda in sequence.  In
general, as the simulation runs, new items will be added to the agenda, and
<code>propagate</code> will continue the simulation as long as there are items on the
agenda:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">propagate</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">empty-agenda? the-agenda</span><span class="clo">)</span><span class="pln">
      </span><span class="lit">'done</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">first-item 
             </span><span class="opn">(</span><span class="pln">first-agenda-item the-agenda</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">first-item</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">remove-first-agenda-item! the-agenda</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">propagate</span><span class="clo">))))</span></pre></div>

<a id="A-sample-simulation"></a>
<h5 class="subsubheading">A sample simulation</h5>

<p>The following procedure, which places a “probe” on a wire, shows the
simulator in action.  The probe tells the wire that, whenever its signal
changes value, it should print the new signal value, together with the current
time and a name that identifies the wire:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">probe name wire</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">add-action! 
   wire
   </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">newline</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">display name</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">display </span><span class="str">" "</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">display </span><span class="opn">(</span><span class="pln">current-time the-agenda</span><span class="clo">))</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">display </span><span class="str">"  New-value = "</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">display </span><span class="opn">(</span><span class="pln">get-signal wire</span><span class="clo">)))))</span></pre></div>

<p>We begin by initializing the agenda and specifying delays for the primitive
function boxes:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> the-agenda </span><span class="opn">(</span><span class="pln">make-agenda</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> inverter-delay </span><span class="lit">2</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> and-gate-delay </span><span class="lit">3</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> or-gate-delay </span><span class="lit">5</span><span class="clo">)</span></pre></div>

<p>Now we define four wires, placing probes on two of them:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> input-1 </span><span class="opn">(</span><span class="pln">make-wire</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> input-2 </span><span class="opn">(</span><span class="pln">make-wire</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> sum </span><span class="opn">(</span><span class="pln">make-wire</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> carry </span><span class="opn">(</span><span class="pln">make-wire</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">probe </span><span class="lit">'sum</span><span class="pln"> sum</span><span class="clo">)</span><span class="pln">
</span><i><span class="pln">sum </span><span class="lit">0</span><span class="pln">  New-value </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">probe </span><span class="lit">'carry</span><span class="pln"> carry</span><span class="clo">)</span><span class="pln">
</span><i><span class="pln">carry </span><span class="lit">0</span><span class="pln">  New-value </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span></i>
</pre></div>

<p>Next we connect the wires in a half-adder circuit (as in <a href="#Figure-3_002e25">Figure 3.25</a>),
set the signal on <code>input-1</code> to 1, and run the simulation:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">half-adder input-1 input-2 sum carry</span><span class="clo">)</span><span class="pln">
</span><i><span class="pln">ok</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">set-signal! input-1 </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
</span><i><span class="pln">done</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">propagate</span><span class="clo">)</span><span class="pln">
</span><i><span class="pln">sum </span><span class="lit">8</span><span class="pln">  New-value </span><span class="pun">=</span><span class="pln"> </span><span class="lit">1</span></i><span class="pln">
</span><i><span class="pln">done</span></i>
</pre></div>

<p>The <code>sum</code> signal changes to 1 at time 8.  We are now eight time units from
the beginning of the simulation.  At this point, we can set the signal on
<code>input-2</code> to 1 and allow the values to propagate:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">set-signal! input-2 </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
</span><i><span class="pln">done</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">propagate</span><span class="clo">)</span><span class="pln">
</span><i><span class="pln">carry </span><span class="lit">11</span><span class="pln">  New-value </span><span class="pun">=</span><span class="pln"> </span><span class="lit">1</span></i><span class="pln">
</span><i><span class="pln">sum </span><span class="lit">16</span><span class="pln">  New-value </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span></i><span class="pln">
</span><i><span class="pln">done</span></i>
</pre></div>

<p>The <code>carry</code> changes to 1 at time 11 and the <code>sum</code> changes to 0 at
time 16.
</p>
<blockquote>
<p><strong><a id="Exercise-3_002e31"></a>Exercise 3.31:</strong> The internal procedure
<code>accept-action-procedure!</code> defined in <code>make-wire</code> specifies that when
a new action procedure is added to a wire, the procedure is immediately run.
Explain why this initialization is necessary.  In particular, trace through the
half-adder example in the paragraphs above and say how the system’s response
would differ if we had defined <code>accept-action-procedure!</code> as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">accept-action-procedure! proc</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> action-procedures 
        </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> proc action-procedures</span><span class="clo">)))</span></pre></div>
</blockquote>

<a id="Implementing-the-agenda"></a>
<h5 class="subsubheading">Implementing the agenda</h5>

<p>Finally, we give details of the agenda data structure, which holds the
procedures that are scheduled for future execution.
</p>
<p>The agenda is made up of <a id="index-time-segments"></a>
<em>time segments</em>.  Each time segment is a pair
consisting of a number (the time) and a queue (see <a href="#Exercise-3_002e32">Exercise 3.32</a>) that
holds the procedures that are scheduled to be run during that time segment.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-time-segment time queue</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> time queue</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">segment-time s</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> s</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">segment-queue s</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> s</span><span class="clo">))</span></pre></div>

<p>We will operate on the time-segment queues using the queue operations described
in <a href="#g_t3_002e3_002e2">3.3.2</a>.
</p>
<p>The agenda itself is a one-dimensional table of time segments.  It differs from
the tables described in <a href="#g_t3_002e3_002e3">3.3.3</a> in that the segments will be sorted
in order of increasing time.  In addition, we store the <a id="index-current-time"></a>
<em>current time</em>
(i.e., the time of the last action that was processed) at the head of the
agenda.  A newly constructed agenda has no time segments and has a current time
of 0:<a class="footnote_link" id="DOCF156" href="#FOOT156"><sup>156</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-agenda</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list </span><span class="lit">0</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">current-time agenda</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> agenda</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">set-current-time! agenda time</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">set-car! agenda time</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">segments agenda</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> agenda</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">set-segments! agenda segments</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">set-cdr! agenda segments</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">first-segment agenda</span><span class="clo">)</span><span class="pln"> 
  </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> </span><span class="opn">(</span><span class="pln">segments agenda</span><span class="clo">)))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">rest-segments agenda</span><span class="clo">)</span><span class="pln"> 
  </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> </span><span class="opn">(</span><span class="pln">segments agenda</span><span class="clo">)))</span></pre></div>

<p>An agenda is empty if it has no time segments:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">empty-agenda? agenda</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">null? </span><span class="opn">(</span><span class="pln">segments agenda</span><span class="clo">)))</span></pre></div>

<p>To add an action to an agenda, we first check if the agenda is empty.  If so,
we create a time segment for the action and install this in the agenda.
Otherwise, we scan the agenda, examining the time of each segment.  If we find
a segment for our appointed time, we add the action to the associated queue.
If we reach a time later than the one to which we are appointed, we insert a
new time segment into the agenda just before it.  If we reach the end of the
agenda, we must create a new time segment at the end.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">add-to-agenda! time action agenda</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">belongs-before? segments</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">or</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? segments</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pun">&lt;</span><span class="pln"> time 
           </span><span class="opn">(</span><span class="pln">segment-time </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> segments</span><span class="clo">)))))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-new-time-segment time action</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">q </span><span class="opn">(</span><span class="pln">make-queue</span><span class="clo">)))</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">insert-queue! q action</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">make-time-segment time q</span><span class="clo">)))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">add-to-segments! segments</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> </span><span class="opn">(</span><span class="pln">segment-time </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> segments</span><span class="clo">))</span><span class="pln"> time</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">insert-queue! 
         </span><span class="opn">(</span><span class="pln">segment-queue </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> segments</span><span class="clo">))</span><span class="pln">
         action</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">rest </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> segments</span><span class="clo">)))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">belongs-before? rest</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">set-cdr!
               segments
               </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-new-time-segment 
                      time 
                      action</span><span class="clo">)</span><span class="pln">
                     </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> segments</span><span class="clo">)))</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">add-to-segments! rest</span><span class="clo">)))))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">segments </span><span class="opn">(</span><span class="pln">segments agenda</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">belongs-before? segments</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">set-segments!
         agenda
         </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-new-time-segment 
                time 
                action</span><span class="clo">)</span><span class="pln">
               segments</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">add-to-segments! segments</span><span class="clo">))))</span></pre></div>

<p>The procedure that removes the first item from the agenda deletes the item at
the front of the queue in the first time segment.  If this deletion makes the
time segment empty, we remove it from the list of segments:<a class="footnote_link" id="DOCF157" href="#FOOT157"><sup>157</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">remove-first-agenda-item! agenda</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">q </span><span class="opn">(</span><span class="pln">segment-queue 
            </span><span class="opn">(</span><span class="pln">first-segment agenda</span><span class="clo">))))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">delete-queue! q</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">empty-queue? q</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">set-segments! 
         agenda 
         </span><span class="opn">(</span><span class="pln">rest-segments agenda</span><span class="clo">)))))</span></pre></div>

<p>The first agenda item is found at the head of the queue in the first time
segment.  Whenever we extract an item, we also update the current
time:<a class="footnote_link" id="DOCF158" href="#FOOT158"><sup>158</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">first-agenda-item agenda</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">empty-agenda? agenda</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Agenda is empty: 
              FIRST-AGENDA-ITEM"</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">first-seg 
             </span><span class="opn">(</span><span class="pln">first-segment agenda</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">set-current-time! 
         agenda 
         </span><span class="opn">(</span><span class="pln">segment-time first-seg</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">front-queue 
         </span><span class="opn">(</span><span class="pln">segment-queue first-seg</span><span class="clo">)))))</span></pre></div>

<blockquote>
<p><strong><a id="Exercise-3_002e32"></a>Exercise 3.32:</strong> The procedures to be run during
each time segment of the agenda are kept in a queue.  Thus, the procedures for
each segment are called in the order in which they were added to the agenda
(first in, first out).  Explain why this order must be used.  In particular,
trace the behavior of an and-gate whose inputs change from 0, 1 to 1, 0 in the
same segment and say how the behavior would differ if we stored a segment’s
procedures in an ordinary list, adding and removing procedures only at the
front (last in, first out).
</p></blockquote>


<a id="g_t3_002e3_002e5"></a>
<a id="Propagation-of-Constraints"></a>
<h4 class="subsection"><span class="secnum">3.3.5</span><span class="sectitle">Propagation of Constraints</span></h4>

<p>Computer programs are traditionally organized as one-directional computations,
which perform operations on prespecified arguments to produce desired outputs.
On the other hand, we often model systems in terms of relations among
quantities.  For example, a mathematical model of a mechanical structure might
include the information that the deflection <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>d</mi>
</math> of a metal rod is related to
the force <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>F</mi>
</math> on the rod, the length <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>L</mi>
</math> of the rod, the cross-sectional
area <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>A</mi>
</math>, and the elastic modulus <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>E</mi>
</math> via the equation
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>d</mi>
    <mi>A</mi>
    <mi>E</mi>
  </mrow>
  <mspace width="thinmathspace"/>
  <mo>=</mo>
  <mspace width="thinmathspace"/>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>F</mi>
    <mi>L</mi>
    <mo>.</mo>
  </mrow>
</math>
Such an equation is not one-directional.  Given any four of the quantities, we
can use it to compute the fifth.  Yet translating the equation into a
traditional computer language would force us to choose one of the quantities to
be computed in terms of the other four.  Thus, a procedure for computing the
area <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>A</mi>
</math> could not be used to compute the deflection <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>d</mi>
</math>, even though the
computations of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>A</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>d</mi>
</math> arise from the same
equation.<a class="footnote_link" id="DOCF159" href="#FOOT159"><sup>159</sup></a>
</p>
<p>In this section, we sketch the design of a language that enables us to work in
terms of relations themselves.  The primitive elements of the language are
<a id="index-primitive-constraints"></a>
<em>primitive constraints</em>, which state that certain relations hold
between quantities.  For example, <code>(adder a b c)</code> specifies that the
quantities <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>b</mi>
</math>, and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>c</mi>
</math> must be related by the equation 
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>a</mi>
    <mo>+</mo>
    <mi>b</mi>
    <mo>=</mo>
    <mi>c</mi>
  </mrow>
</math>, <code>(multiplier x y z)</code> expresses the constraint 
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>x</mi>
    <mi>y</mi>
    <mo>=</mo>
    <mi>z</mi>
  </mrow>
</math>, and <code>(constant 3.14 x)</code> says that the value of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> must be 3.14.
</p>
<p>Our language provides a means of combining primitive constraints in order to
express more complex relations.  We combine constraints by constructing
<a id="index-constraint-networks"></a>
<em>constraint networks</em>, in which constraints are joined by
<a id="index-connectors"></a>
<em>connectors</em>.  A connector is an object that “holds” a value that may
participate in one or more constraints.  For example, we know that the
relationship between Fahrenheit and Celsius temperatures is
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>9</mn>
    <mi>C</mi>
  </mrow>
  <mspace width="thinmathspace"/>
  <mo>=</mo>
  <mspace width="thinmathspace"/>
  <mrow class="MJX-TeXAtom-ORD">
    <mn>5</mn>
    <mo stretchy="false">(</mo>
    <mi>F</mi>
    <mo>−<!-- − --></mo>
    <mn>32</mn>
    <mo stretchy="false">)</mo>
    <mo>.</mo>
  </mrow>
</math>
Such a constraint can be thought of as a network consisting of primitive adder,
multiplier, and constant constraints (<a href="#Figure-3_002e28">Figure 3.28</a>).  In the figure, we
see on the left a multiplier box with three terminals, labeled <math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mi>m</mi>
  <mn>1</mn>
</mrow>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mi>m</mi>
  <mn>2</mn>
</mrow>
</math>,
and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>p</mi>
</math>.  These connect the multiplier to the rest of the network as follows:
The <math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mi>m</mi>
  <mn>1</mn>
</mrow>
</math> terminal is linked to a connector <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>C</mi>
</math>, which will hold the Celsius
temperature.  The <math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mi>m</mi>
  <mn>2</mn>
</mrow>
</math> terminal is linked to a connector <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>w</mi>
</math>, which is also
linked to a constant box that holds 9.  The <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>p</mi>
</math> terminal, which the
multiplier box constrains to be the product of <math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mi>m</mi>
  <mn>1</mn>
</mrow>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mi>m</mi>
  <mn>2</mn>
</mrow>
</math>, is linked to
the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>p</mi>
</math> terminal of another multiplier box, whose <math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mi>m</mi>
  <mn>2</mn>
</mrow>
</math> is connected to a
constant 5 and whose <math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mi>m</mi>
  <mn>1</mn>
</mrow>
</math> is connected to one of the terms in a sum.
</p>
<figure class="float">
<a id="Figure-3_002e28"></a>
<object style="width: 58.11ex; height: 18.30ex;" data="fig/chap3/Fig3.28.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.28:</strong> The relation <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>9</mn>
    <mi>C</mi>
    <mo>=</mo>
    <mn>5</mn>
    <mo stretchy="false">(</mo>
    <mi>F</mi>
    <mo>−<!-- − --></mo>
    <mn>32</mn>
    <mo stretchy="false">)</mo>
  </mrow>
</math> expressed as a constraint network.</p>
</figcaption>
</figure>

<p>Computation by such a network proceeds as follows: When a connector is given a
value (by the user or by a constraint box to which it is linked), it awakens
all of its associated constraints (except for the constraint that just awakened
it) to inform them that it has a value.  Each awakened constraint box then
polls its connectors to see if there is enough information to determine a value
for a connector.  If so, the box sets that connector, which then awakens all of
its associated constraints, and so on.  For instance, in conversion between
Celsius and Fahrenheit, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>w</mi>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math>, and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
</math> are immediately set by the
constant boxes to 9, 5, and 32, respectively.  The connectors awaken the
multipliers and the adder, which determine that there is not enough information
to proceed.  If the user (or some other part of the network) sets <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>C</mi>
</math> to a
value (say 25), the leftmost multiplier will be awakened, and it will set <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>u</mi>
</math>
to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>25</mn>
    <mo>⋅<!-- ⋅ --></mo>
    <mn>9</mn>
    <mo>=</mo>
    <mn>225</mn>
  </mrow>
</math>.  Then <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>u</mi>
</math> awakens the second multiplier, which sets <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>v</mi>
</math> to
45, and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>v</mi>
</math> awakens the adder, which sets <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>F</mi>
</math> to 77.
</p>
<a id="Using-the-constraint-system"></a>
<h5 class="subsubheading">Using the constraint system</h5>

<p>To use the constraint system to carry out the temperature computation outlined
above, we first create two connectors, <code>C</code> and <code>F</code>, by calling the
constructor <code>make-connector</code>, and link <code>C</code> and <code>F</code> in an
appropriate network:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> C </span><span class="opn">(</span><span class="pln">make-connector</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> F </span><span class="opn">(</span><span class="pln">make-connector</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">celsius-fahrenheit-converter C F</span><span class="clo">)</span><span class="pln">
</span><i><span class="pln">ok</span></i>
</pre></div>

<p>The procedure that creates the network is defined as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">celsius-fahrenheit-converter c f</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">u </span><span class="opn">(</span><span class="pln">make-connector</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">v </span><span class="opn">(</span><span class="pln">make-connector</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">w </span><span class="opn">(</span><span class="pln">make-connector</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">x </span><span class="opn">(</span><span class="pln">make-connector</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">y </span><span class="opn">(</span><span class="pln">make-connector</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">multiplier c w u</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">multiplier v x u</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">adder v y f</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">constant </span><span class="lit">9</span><span class="pln"> w</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">constant </span><span class="lit">5</span><span class="pln"> x</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">constant </span><span class="lit">32</span><span class="pln"> y</span><span class="clo">)</span><span class="pln">
    </span><span class="lit">'ok</span><span class="clo">))</span></pre></div>

<p>This procedure creates the internal connectors <code>u</code>, <code>v</code>, <code>w</code>,
<code>x</code>, and <code>y</code>, and links them as shown in <a href="#Figure-3_002e28">Figure 3.28</a> using the
primitive constraint constructors <code>adder</code>, <code>multiplier</code>, and
<code>constant</code>.  Just as with the digital-circuit simulator of 
<a href="#g_t3_002e3_002e4">3.3.4</a>, expressing these combinations of primitive elements in terms of
procedures automatically provides our language with a means of abstraction for
compound objects.
</p>
<p>To watch the network in action, we can place probes on the connectors <code>C</code>
and <code>F</code>, using a <code>probe</code> procedure similar to the one we used to
monitor wires in <a href="#g_t3_002e3_002e4">3.3.4</a>.  Placing a probe on a connector will
cause a message to be printed whenever the connector is given a value:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">probe </span><span class="str">"Celsius temp"</span><span class="pln"> C</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">probe </span><span class="str">"Fahrenheit temp"</span><span class="pln"> F</span><span class="clo">)</span></pre></div>

<p>Next we set the value of <code>C</code> to 25.  (The third argument to
<code>set-value!</code> tells <code>C</code> that this directive comes from the
<code>user</code>.)
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">set-value! C </span><span class="lit">25</span><span class="pln"> </span><span class="lit">'user</span><span class="clo">)</span><span class="pln">
</span><i><span class="pln">Probe</span><span class="pun">:</span><span class="pln"> Celsius temp </span><span class="pun">=</span><span class="pln"> </span><span class="lit">25</span></i><span class="pln">
</span><i><span class="pln">Probe</span><span class="pun">:</span><span class="pln"> Fahrenheit temp </span><span class="pun">=</span><span class="pln"> </span><span class="lit">77</span></i><span class="pln">
</span><i><span class="pln">done</span></i>
</pre></div>

<p>The probe on <code>C</code> awakens and reports the value.  <code>C</code> also propagates
its value through the network as described above.  This sets <code>F</code> to 77,
which is reported by the probe on <code>F</code>.
</p>
<p>Now we can try to set <code>F</code> to a new value, say 212:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">set-value! F </span><span class="lit">212</span><span class="pln"> </span><span class="lit">'user</span><span class="clo">)</span><span class="pln">
</span><i><span class="pln">Error! Contradiction </span><span class="opn">(</span><span class="lit">77</span><span class="pln"> </span><span class="lit">212</span><span class="clo">)</span></i>
</pre></div>

<p>The connector complains that it has sensed a contradiction: Its value is 77,
and someone is trying to set it to 212.  If we really want to reuse the network
with new values, we can tell <code>C</code> to forget its old value:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">forget-value! C </span><span class="lit">'user</span><span class="clo">)</span><span class="pln">
</span><i><span class="pln">Probe</span><span class="pun">:</span><span class="pln"> Celsius temp </span><span class="pun">=</span><span class="pln"> </span><span class="pun">?</span></i><span class="pln">
</span><i><span class="pln">Probe</span><span class="pun">:</span><span class="pln"> Fahrenheit temp </span><span class="pun">=</span><span class="pln"> </span><span class="pun">?</span></i><span class="pln">
</span><i><span class="pln">done</span></i>
</pre></div>

<p><code>C</code> finds that the <code>user</code>, who set its value originally, is now
retracting that value, so <code>C</code> agrees to lose its value, as shown by the
probe, and informs the rest of the network of this fact.  This information
eventually propagates to <code>F</code>, which now finds that it has no reason for
continuing to believe that its own value is 77.  Thus, <code>F</code> also gives up
its value, as shown by the probe.
</p>
<p>Now that <code>F</code> has no value, we are free to set it to 212:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">set-value! F </span><span class="lit">212</span><span class="pln"> </span><span class="lit">'user</span><span class="clo">)</span><span class="pln">
</span><i><span class="pln">Probe</span><span class="pun">:</span><span class="pln"> Fahrenheit temp </span><span class="pun">=</span><span class="pln"> </span><span class="lit">212</span></i><span class="pln">
</span><i><span class="pln">Probe</span><span class="pun">:</span><span class="pln"> Celsius temp </span><span class="pun">=</span><span class="pln"> </span><span class="lit">100</span></i><span class="pln">
</span><i><span class="pln">done</span></i>
</pre></div>

<p>This new value, when propagated through the network, forces <code>C</code> to have a
value of 100, and this is registered by the probe on <code>C</code>.  Notice that the
very same network is being used to compute <code>C</code> given <code>F</code> and to
compute <code>F</code> given <code>C</code>.  This nondirectionality of computation is the
distinguishing feature of constraint-based systems.
</p>
<a id="Implementing-the-constraint-system"></a>
<h5 class="subsubheading">Implementing the constraint system</h5>

<p>The constraint system is implemented via procedural objects with local state,
in a manner very similar to the digital-circuit simulator of 
<a href="#g_t3_002e3_002e4">3.3.4</a>.  Although the primitive objects of the constraint system are
somewhat more complex, the overall system is simpler, since there is no concern
about agendas and logic delays.
</p>
<p>The basic operations on connectors are the following:
</p>
<ul>
<li> <code>(has-value? ⟨<var>connector</var>⟩)</code> tells whether the connector has a value.

</li><li> <code>(get-value ⟨<var>connector</var>⟩)</code> returns the connector’s current value.

</li><li> <code>(set-value! ⟨<var>connector</var>⟩ ⟨<var>new-value</var>⟩ ⟨<var>informant</var>⟩)</code>
indicates that the informant is requesting the connector to set its value to
the new value.

</li><li> <code>(forget-value! ⟨<var>connector</var>⟩ ⟨<var>retractor</var>⟩)</code> tells the connector
that the retractor is requesting it to forget its value.

</li><li> <code>(connect ⟨<var>connector</var>⟩ ⟨<var>new-constraint</var>⟩)</code> tells the connector
to participate in the new constraint.

</li></ul>

<p>The connectors communicate with the constraints by means of the procedures
<code>inform-about-value</code>, which tells the given constraint that the connector
has a value, and <code>inform-about-no-value</code>, which tells the constraint that
the connector has lost its value.
</p>
<p><code>Adder</code> constructs an adder constraint among summand connectors <code>a1</code>
and <code>a2</code> and a <code>sum</code> connector.  An adder is implemented as a
procedure with local state (the procedure <code>me</code> below):
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">adder a1 a2 sum</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">process-new-value</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">has-value? a1</span><span class="clo">)</span><span class="pln"> 
                </span><span class="opn">(</span><span class="pln">has-value? a2</span><span class="clo">))</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">set-value! sum
                       </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">get-value a1</span><span class="clo">)</span><span class="pln"> 
                          </span><span class="opn">(</span><span class="pln">get-value a2</span><span class="clo">))</span><span class="pln">
                       me</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">((</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">has-value? a1</span><span class="clo">)</span><span class="pln"> 
                </span><span class="opn">(</span><span class="pln">has-value? sum</span><span class="clo">))</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">set-value! a2
                       </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> </span><span class="opn">(</span><span class="pln">get-value sum</span><span class="clo">)</span><span class="pln"> 
                          </span><span class="opn">(</span><span class="pln">get-value a1</span><span class="clo">))</span><span class="pln">
                       me</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">((</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">has-value? a2</span><span class="clo">)</span><span class="pln"> 
                </span><span class="opn">(</span><span class="pln">has-value? sum</span><span class="clo">))</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">set-value! a1
                       </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> </span><span class="opn">(</span><span class="pln">get-value sum</span><span class="clo">)</span><span class="pln"> 
                          </span><span class="opn">(</span><span class="pln">get-value a2</span><span class="clo">))</span><span class="pln">
                       me</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">process-forget-value</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">forget-value! sum me</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">forget-value! a1 me</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">forget-value! a2 me</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">process-new-value</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">me request</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> request </span><span class="lit">'I-have-a-value</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">process-new-value</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> request </span><span class="lit">'I-lost-my-value</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">process-forget-value</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unknown request: 
                        ADDER"</span><span class="pln"> request</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">connect a1 me</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">connect a2 me</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">connect sum me</span><span class="clo">)</span><span class="pln">
  me</span><span class="clo">)</span></pre></div>

<p><code>Adder</code> connects the new adder to the designated connectors and returns it
as its value.  The procedure <code>me</code>, which represents the adder, acts as a
dispatch to the local procedures.  The following “syntax interfaces” (see
<a href="#Footnote-155">Footnote 155</a> in <a href="#g_t3_002e3_002e4">3.3.4</a>) are used in conjunction with
the dispatch:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">inform-about-value constraint</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">constraint </span><span class="lit">'I-have-a-value</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">inform-about-no-value constraint</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">constraint </span><span class="lit">'I-lost-my-value</span><span class="clo">))</span></pre></div>

<p>The adder’s local procedure <code>process-new-value</code> is called when the adder
is informed that one of its connectors has a value. The adder first checks to
see if both <code>a1</code> and <code>a2</code> have values. If so, it tells <code>sum</code> to
set its value to the sum of the two addends.  The <code>informant</code> argument to
<code>set-value!</code> is <code>me</code>, which is the adder object itself.  If <code>a1</code>
and <code>a2</code> do not both have values, then the adder checks to see if perhaps
<code>a1</code> and <code>sum</code> have values.  If so, it sets <code>a2</code> to the
difference of these two.  Finally, if <code>a2</code> and <code>sum</code> have values,
this gives the adder enough information to set <code>a1</code>.  If the adder is told
that one of its connectors has lost a value, it requests that all of its
connectors now lose their values.  (Only those values that were set by this
adder are actually lost.)  Then it runs <code>process-new-value</code>.  The reason
for this last step is that one or more connectors may still have a value (that
is, a connector may have had a value that was not originally set by the adder),
and these values may need to be propagated back through the adder.
</p>
<p>A multiplier is very similar to an adder. It will set its <code>product</code> to 0
if either of the factors is 0, even if the other factor is not known.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">multiplier m1 m2 product</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">process-new-value</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">or</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">has-value? m1</span><span class="clo">)</span><span class="pln"> 
                    </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> </span><span class="opn">(</span><span class="pln">get-value m1</span><span class="clo">)</span><span class="pln"> </span><span class="lit">0</span><span class="clo">))</span><span class="pln">
               </span><span class="opn">(</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">has-value? m2</span><span class="clo">)</span><span class="pln"> 
                    </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> </span><span class="opn">(</span><span class="pln">get-value m2</span><span class="clo">)</span><span class="pln"> </span><span class="lit">0</span><span class="clo">)))</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">set-value! product </span><span class="lit">0</span><span class="pln"> me</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">((</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">has-value? m1</span><span class="clo">)</span><span class="pln"> 
                </span><span class="opn">(</span><span class="pln">has-value? m2</span><span class="clo">))</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">set-value! product
                       </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pln">get-value m1</span><span class="clo">)</span><span class="pln"> 
                          </span><span class="opn">(</span><span class="pln">get-value m2</span><span class="clo">))</span><span class="pln">
                       me</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">((</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">has-value? product</span><span class="clo">)</span><span class="pln"> 
                </span><span class="opn">(</span><span class="pln">has-value? m1</span><span class="clo">))</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">set-value! m2
                       </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> </span><span class="opn">(</span><span class="pln">get-value product</span><span class="clo">)</span><span class="pln"> 
                          </span><span class="opn">(</span><span class="pln">get-value m1</span><span class="clo">))</span><span class="pln">
                       me</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">((</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">has-value? product</span><span class="clo">)</span><span class="pln"> 
                </span><span class="opn">(</span><span class="pln">has-value? m2</span><span class="clo">))</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">set-value! m1
                       </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> </span><span class="opn">(</span><span class="pln">get-value product</span><span class="clo">)</span><span class="pln"> 
                          </span><span class="opn">(</span><span class="pln">get-value m2</span><span class="clo">))</span><span class="pln">
                       me</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">process-forget-value</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">forget-value! product me</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">forget-value! m1 me</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">forget-value! m2 me</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">process-new-value</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">me request</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> request </span><span class="lit">'I-have-a-value</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">process-new-value</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> request </span><span class="lit">'I-lost-my-value</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">process-forget-value</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">else</span><span class="pln">
           </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unknown request: 
                   MULTIPLIER"</span><span class="pln"> 
                  request</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">connect m1 me</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">connect m2 me</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">connect product me</span><span class="clo">)</span><span class="pln">
  me</span><span class="clo">)</span></pre></div>

<p>A <code>constant</code> constructor simply sets the value of the designated
connector.  Any <code>I-have-a-value</code> or <code>I-lost-my-value</code> message sent to
the constant box will produce an error.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">constant value connector</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">me request</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unknown request: CONSTANT"</span><span class="pln"> 
           request</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">connect connector me</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">set-value! connector value me</span><span class="clo">)</span><span class="pln">
  me</span><span class="clo">)</span></pre></div>

<p>Finally, a probe prints a message about the setting or unsetting of
the designated connector:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">probe name connector</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">print-probe value</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">newline</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">display </span><span class="str">"Probe: "</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">display name</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">display </span><span class="str">" = "</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">display value</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">process-new-value</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">print-probe </span><span class="opn">(</span><span class="pln">get-value connector</span><span class="clo">)))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">process-forget-value</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">print-probe </span><span class="str">"?"</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">me request</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> request </span><span class="lit">'I-have-a-value</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">process-new-value</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> request </span><span class="lit">'I-lost-my-value</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">process-forget-value</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unknown request: 
                        PROBE"</span><span class="pln"> request</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">connect connector me</span><span class="clo">)</span><span class="pln">
  me</span><span class="clo">)</span></pre></div>

<a id="Representing-connectors"></a>
<h5 class="subsubheading">Representing connectors</h5>

<p>A connector is represented as a procedural object with local state variables
<code>value</code>, the current value of the connector; <code>informant</code>, the object
that set the connector’s value; and <code>constraints</code>, a list of the
constraints in which the connector participates.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-connector</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">value false</span><span class="clo">)</span><span class="pln"> 
        </span><span class="opn">(</span><span class="pln">informant false</span><span class="clo">)</span><span class="pln"> 
        </span><span class="opn">(</span><span class="pln">constraints </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">set-my-value newval setter</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">not </span><span class="opn">(</span><span class="pln">has-value? me</span><span class="clo">))</span><span class="pln">
             </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> value newval</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> informant setter</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">for-each-except 
              setter
              inform-about-value
              constraints</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">((</span><span class="pln">not </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> value newval</span><span class="clo">))</span><span class="pln">
             </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Contradiction"</span><span class="pln"> 
                    </span><span class="opn">(</span><span class="pln">list value newval</span><span class="clo">)))</span><span class="pln">
            </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="lit">'ignored</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">forget-my-value retractor</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> retractor informant</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">begin</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> informant false</span><span class="clo">)</span><span class="pln">
                 </span><span class="opn">(</span><span class="pln">for-each-except 
                  retractor
                  inform-about-no-value
                  constraints</span><span class="clo">))</span><span class="pln">
          </span><span class="lit">'ignored</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">connect new-constraint</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">not </span><span class="opn">(</span><span class="pln">memq new-constraint 
                     constraints</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> constraints
                </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> new-constraint 
                      constraints</span><span class="clo">)))</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">has-value? me</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">inform-about-value new-constraint</span><span class="clo">))</span><span class="pln">
      </span><span class="lit">'done</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">me request</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> request </span><span class="lit">'has-value?</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> informant true false</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> request </span><span class="lit">'value</span><span class="clo">)</span><span class="pln"> value</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> request </span><span class="lit">'set-value!</span><span class="clo">)</span><span class="pln"> 
             set-my-value</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> request </span><span class="lit">'forget</span><span class="clo">)</span><span class="pln"> 
             forget-my-value</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> request </span><span class="lit">'connect</span><span class="clo">)</span><span class="pln"> connect</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unknown operation: 
                          CONNECTOR"</span><span class="pln">
                         request</span><span class="clo">))))</span><span class="pln">
    me</span><span class="clo">))</span></pre></div>

<p>The connector’s local procedure <code>set-my-value</code> is called when there is a
request to set the connector’s value.  If the connector does not currently have
a value, it will set its value and remember as <code>informant</code> the constraint
that requested the value to be set.<a class="footnote_link" id="DOCF160" href="#FOOT160"><sup>160</sup></a>  Then the connector will notify all of its participating
constraints except the constraint that requested the value to be set.  This is
accomplished using the following iterator, which applies a designated procedure
to all items in a list except a given one:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">for-each-except exception 
                         procedure 
                         list</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">loop items</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">null? items</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'done</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> items</span><span class="clo">)</span><span class="pln"> exception</span><span class="clo">)</span><span class="pln"> 
           </span><span class="opn">(</span><span class="pln">loop </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> items</span><span class="clo">)))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="pln">procedure </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> items</span><span class="clo">))</span><span class="pln">
                </span><span class="opn">(</span><span class="pln">loop </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> items</span><span class="clo">)))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">loop list</span><span class="clo">))</span></pre></div>

<p>If a connector is asked to forget its value, it runs the local procedure
<code>forget-my-value</code>, which first checks to make sure that the request is
coming from the same object that set the value originally.  If so, the
connector informs its associated constraints about the loss of the value.
</p>
<p>The local procedure <code>connect</code> adds the designated new constraint to the
list of constraints if it is not already in that list.  Then, if the connector
has a value, it informs the new constraint of this fact.
</p>
<p>The connector’s procedure <code>me</code> serves as a dispatch to the other internal
procedures and also represents the connector as an object.  The following
procedures provide a syntax interface for the dispatch:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">has-value? connector</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">connector </span><span class="lit">'has-value?</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">get-value connector</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">connector </span><span class="lit">'value</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">set-value! connector 
                    new-value 
                    informant</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">((</span><span class="pln">connector </span><span class="lit">'set-value!</span><span class="clo">)</span><span class="pln"> 
   new-value 
   informant</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">forget-value! connector retractor</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">((</span><span class="pln">connector </span><span class="lit">'forget</span><span class="clo">)</span><span class="pln"> retractor</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">connect connector new-constraint</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">((</span><span class="pln">connector </span><span class="lit">'connect</span><span class="clo">)</span><span class="pln"> new-constraint</span><span class="clo">))</span></pre></div>

<blockquote>
<p><strong><a id="Exercise-3_002e33"></a>Exercise 3.33:</strong> Using primitive multiplier,
adder, and constant constraints, define a procedure <code>averager</code> that takes
three connectors <code>a</code>, <code>b</code>, and <code>c</code> as inputs and establishes the
constraint that the value of <code>c</code> is the average of the values of <code>a</code>
and <code>b</code>.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e34"></a>Exercise 3.34:</strong> Louis Reasoner wants to build a
squarer, a constraint device with two terminals such that the value of
connector <code>b</code> on the second terminal will always be the square of the
value <code>a</code> on the first terminal.  He proposes the following simple device
made from a multiplier:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">squarer a b</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">multiplier a a b</span><span class="clo">))</span></pre></div>

<p>There is a serious flaw in this idea.  Explain.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e35"></a>Exercise 3.35:</strong> Ben Bitdiddle tells Louis that
one way to avoid the trouble in <a href="#Exercise-3_002e34">Exercise 3.34</a> is to define a squarer as a
new primitive constraint.  Fill in the missing portions in Ben’s outline for a
procedure to implement such a constraint:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">squarer a b</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">process-new-value</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">has-value? b</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&lt;</span><span class="pln"> </span><span class="opn">(</span><span class="pln">get-value b</span><span class="clo">)</span><span class="pln"> </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"square less than 0: 
                    SQUARER"</span><span class="pln"> 
                   </span><span class="opn">(</span><span class="pln">get-value b</span><span class="clo">))</span><span class="pln">
            ⟨</span><var><span class="pln">alternative1</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln">
        ⟨</span><var><span class="pln">alternative2</span></var><span class="pln">⟩</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">process-forget-value</span><span class="clo">)</span><span class="pln"> ⟨</span><var><span class="pln">body1</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">me request</span><span class="clo">)</span><span class="pln"> ⟨</span><var><span class="pln">body2</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln">
  ⟨</span><var><span class="pln">rest of definition</span></var><span class="pln">⟩
  me</span><span class="clo">)</span></pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e36"></a>Exercise 3.36:</strong> Suppose we evaluate the following
sequence of expressions in the global environment:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> a </span><span class="opn">(</span><span class="pln">make-connector</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> b </span><span class="opn">(</span><span class="pln">make-connector</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">set-value! a </span><span class="lit">10</span><span class="pln"> </span><span class="lit">'user</span><span class="clo">)</span></pre></div>

<p>At some time during evaluation of the <code>set-value!</code>, the following
expression from the connector’s local procedure is evaluated:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">for-each-except 
  setter inform-about-value constraints</span><span class="clo">)</span></pre></div>

<p>Draw an environment diagram showing the environment in which the above
expression is evaluated.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e37"></a>Exercise 3.37:</strong> The
<code>celsius-fahrenheit-converter</code> procedure is cumbersome when compared with
a more expression-oriented style of definition, such as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">celsius-fahrenheit-converter x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">c</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">c</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pln">c</span><span class="pun">/</span><span class="pln"> </span><span class="opn">(</span><span class="pln">cv </span><span class="lit">9</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">cv </span><span class="lit">5</span><span class="clo">))</span><span class="pln">
          x</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">cv </span><span class="lit">32</span><span class="clo">)))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> C </span><span class="opn">(</span><span class="pln">make-connector</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> F </span><span class="opn">(</span><span class="pln">celsius-fahrenheit-converter C</span><span class="clo">))</span></pre></div>

<p>Here <code>c+</code>, <code>c*</code>, etc. are the “constraint” versions of the
arithmetic operations.  For example, <code>c+</code> takes two connectors as
arguments and returns a connector that is related to these by an adder
constraint:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">c</span><span class="pun">+</span><span class="pln"> x y</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">z </span><span class="opn">(</span><span class="pln">make-connector</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">adder x y z</span><span class="clo">)</span><span class="pln">
    z</span><span class="clo">))</span></pre></div>

<p>Define analogous procedures <code>c-</code>, <code>c*</code>, <code>c/</code>, and <code>cv</code>
(constant value) that enable us to define compound constraints as in the
converter example above.<a class="footnote_link" id="DOCF161" href="#FOOT161"><sup>161</sup></a>
</p></blockquote>

<div class="footnote">
<h4 class="footnotes-heading">Footnotes</h4>

<div id="FOOT144"><p><a class="footnote_backlink" href="#DOCF144"><sup>144</sup></a>
<code>Set-car!</code> and
<code>set-cdr!</code> return implementation-dependent values.  Like <code>set!</code>, they
should be used only for their effect.</p>
</div>
<div id="FOOT145"><p><a class="footnote_backlink" href="#DOCF145"><sup>145</sup></a>
We see from
this that mutation operations on lists can create “garbage” that is not part
of any accessible structure.  We will see in <a href="5_002e3.xhtml#g_t5_002e3_002e2">5.3.2</a> that Lisp
memory-management systems include a <a id="index-garbage-collector"></a>
<em>garbage collector</em>, which
identifies and recycles the memory space used by unneeded pairs.</p>
</div>
<div id="FOOT146"><p><a class="footnote_backlink" href="#DOCF146"><sup>146</sup></a>
<code>Get-new-pair</code> is one of the operations that
must be implemented as part of the memory management required by a Lisp
implementation.  We will discuss this in <a href="5_002e3.xhtml#g_t5_002e3_002e1">5.3.1</a>.</p>
</div>
<div id="FOOT147"><p><a class="footnote_backlink" href="#DOCF147"><sup>147</sup></a>
The two pairs are distinct
because each call to <code>cons</code> returns a new pair.  The symbols are shared;
in Scheme there is a unique symbol with any given name.  Since Scheme provides
no way to mutate a symbol, this sharing is undetectable.  Note also that the
sharing is what enables us to compare symbols using <code>eq?</code>, which simply
checks equality of pointers.</p>
</div>
<div id="FOOT148"><p><a class="footnote_backlink" href="#DOCF148"><sup>148</sup></a>
The subtleties of
dealing with sharing of mutable data objects reflect the underlying issues of
“sameness” and “change” that were raised in <a href="3_002e1.xhtml#g_t3_002e1_002e3">3.1.3</a>.  We
mentioned there that admitting change to our language requires that a compound
object must have an “identity” that is something different from the pieces
from which it is composed.  In Lisp, we consider this “identity” to be the
quality that is tested by <code>eq?</code>, i.e., by equality of pointers.  Since in
most Lisp implementations a pointer is essentially a memory address, we are
“solving the problem” of defining the identity of objects by stipulating that
a data object “itself” is the information stored in some particular set of
memory locations in the computer.  This suffices for simple Lisp programs, but
is hardly a general way to resolve the issue of “sameness” in computational
models.</p>
</div>
<div id="FOOT149"><p><a class="footnote_backlink" href="#DOCF149"><sup>149</sup></a>
On
the other hand, from the viewpoint of implementation, assignment requires us to
modify the environment, which is itself a mutable data structure.  Thus,
assignment and mutation are equipotent: Each can be implemented in terms of the
other.</p>
</div>
<div id="FOOT150"><p><a class="footnote_backlink" href="#DOCF150"><sup>150</sup></a>
If the first item is the final item in the queue, the front
pointer will be the empty list after the deletion, which will mark the queue as
empty; we needn’t worry about updating the rear pointer, which will still point
to the deleted item, because <code>empty-queue?</code> looks only at the front
pointer.</p>
</div>
<div id="FOOT151"><p><a class="footnote_backlink" href="#DOCF151"><sup>151</sup></a>
Be careful not to make the
interpreter try to print a structure that contains cycles.  (See <a href="#Exercise-3_002e13">Exercise 3.13</a>.)</p>
</div>
<div id="FOOT152"><p><a class="footnote_backlink" href="#DOCF152"><sup>152</sup></a>
Because <code>assoc</code>
uses <code>equal?</code>, it can recognize keys that are symbols, numbers, or list
structure.</p>
</div>
<div id="FOOT153"><p><a class="footnote_backlink" href="#DOCF153"><sup>153</sup></a>
Thus, the first
backbone pair is the object that represents the table “itself”; that is, a
pointer to the table is a pointer to this pair.  This same backbone pair always
starts the table.  If we did not arrange things in this way, <code>insert!</code>
would have to return a new value for the start of the table when it added a new
record.</p>
</div>
<div id="FOOT154"><p><a class="footnote_backlink" href="#DOCF154"><sup>154</sup></a>
A full-adder is a basic circuit element used in adding
two binary numbers.  Here A and B are the bits at corresponding positions in
the two numbers to be added, and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi mathvariant="normal">C</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mi mathvariant="normal">i</mi>
      <mi mathvariant="normal">n</mi>
    </mrow>
  </msub>
</math> is the carry bit from the
addition one place to the right.  The circuit generates SUM, which is the sum
bit in the corresponding position, and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi mathvariant="normal">C</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mi mathvariant="normal">o</mi>
      <mi mathvariant="normal">u</mi>
      <mi mathvariant="normal">t</mi>
    </mrow>
  </msub>
</math>, which is the carry
bit to be propagated to the left.</p>
</div>
<div id="FOOT155"><p><a class="footnote_backlink" href="#DOCF155"><sup>155</sup></a>
<a id="Footnote-155"></a>These procedures are simply
syntactic sugar that allow us to use ordinary procedural syntax to access the
local procedures of objects.  It is striking that we can interchange the role
of “procedures” and “data” in such a simple way.  For example, if we write
<code>(wire 'get-signal)</code> we think of <code>wire</code> as a procedure that is called
with the message <code>get-signal</code> as input.  Alternatively, writing
<code>(get-signal wire)</code> encourages us to think of <code>wire</code> as a data object
that is the input to a procedure <code>get-signal</code>.  The truth of the matter is
that, in a language in which we can deal with procedures as objects, there is
no fundamental difference between “procedures” and “data,” and we can
choose our syntactic sugar to allow us to program in whatever style we choose.</p>
</div>
<div id="FOOT156"><p><a class="footnote_backlink" href="#DOCF156"><sup>156</sup></a>
The agenda is a headed list, like the tables in 
<a href="#g_t3_002e3_002e3">3.3.3</a>, but since the list is headed by the time, we do not need an
additional dummy header (such as the <code>*table*</code> symbol used with tables).</p>
</div>
<div id="FOOT157"><p><a class="footnote_backlink" href="#DOCF157"><sup>157</sup></a>
Observe
that the <code>if</code> expression in this procedure has no <code>⟨</code><var>alternative</var><code>⟩</code>
expression.  Such a “one-armed <code>if</code> statement” is used to decide whether
to do something, rather than to select between two expressions.  An <code>if</code>
expression returns an unspecified value if the predicate is false and there is
no <code>⟨</code><var>alternative</var><code>⟩</code>.</p>
</div>
<div id="FOOT158"><p><a class="footnote_backlink" href="#DOCF158"><sup>158</sup></a>
In this way, the current time will always be the time of the
action most recently processed.  Storing this time at the head of the agenda
ensures that it will still be available even if the associated time segment has
been deleted.</p>
</div>
<div id="FOOT159"><p><a class="footnote_backlink" href="#DOCF159"><sup>159</sup></a>
Constraint propagation first appeared in the incredibly
forward-looking <abbr>SKETCHPAD</abbr> system of Ivan <a href="References.xhtml#Sutherland-_00281963_0029">Sutherland (1963)</a>.  A
beautiful constraint-propagation system based on the Smalltalk language was
developed by Alan <a href="References.xhtml#Borning-_00281977_0029">Borning (1977)</a> at Xerox Palo Alto Research Center.  Sussman,
Stallman, and Steele applied constraint propagation to electrical circuit
analysis (<a href="References.xhtml#Sussman-and-Stallman-1975">Sussman and Stallman 1975</a>; <a href="References.xhtml#Sussman-and-Steele-1980">Sussman and Steele 1980</a>). TK!Solver
(<a href="References.xhtml#Konopasek-and-Jayaraman-1984">Konopasek and Jayaraman 1984</a>) is an extensive modeling environment based on
constraints.</p>
</div>
<div id="FOOT160"><p><a class="footnote_backlink" href="#DOCF160"><sup>160</sup></a>
The <code>setter</code> might not be a
constraint.  In our temperature example, we used <code>user</code> as the
<code>setter</code>.</p>
</div>
<div id="FOOT161"><p><a class="footnote_backlink" href="#DOCF161"><sup>161</sup></a>
The expression-oriented format is convenient
because it avoids the need to name the intermediate expressions in a
computation.  Our original formulation of the constraint language is cumbersome
in the same way that many languages are cumbersome when dealing with operations
on compound data.  For example, if we wanted to compute the product 
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>a</mi>
    <mo>+</mo>
    <mi>b</mi>
    <mo stretchy="false">)</mo>
    <mo>⋅<!-- ⋅ --></mo>
    <mo stretchy="false">(</mo>
    <mi>c</mi>
    <mo>+</mo>
    <mi>d</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>, where the variables represent vectors, we could work
in “imperative style,” using procedures that set the values of designated
vector arguments but do not themselves return vectors as values:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">v-sum a b temp1</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">v-sum c d temp2</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">v-prod temp1 temp2 answer</span><span class="clo">)</span></pre></div>

<p>Alternatively, we could deal with expressions, using procedures that return
vectors as values, and thus avoid explicitly mentioning <code>temp1</code> and
<code>temp2</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> answer 
  </span><span class="opn">(</span><span class="pln">v-prod </span><span class="opn">(</span><span class="pln">v-sum a b</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">v-sum c d</span><span class="clo">)))</span></pre></div>

<p>Since Lisp allows us to return compound objects as values of procedures, we can
transform our imperative-style constraint language into an expression-oriented
style as shown in this exercise.  In languages that are impoverished in
handling compound objects, such as Algol, Basic, and Pascal (unless one
explicitly uses Pascal pointer variables), one is usually stuck with the
imperative style when manipulating compound objects.  Given the advantage of
the expression-oriented format, one might ask if there is any reason to have
implemented the system in imperative style, as we did in this section.  One
reason is that the non-expression-oriented constraint language provides a
handle on constraint objects (e.g., the value of the <code>adder</code> procedure) as
well as on connector objects.  This is useful if we wish to extend the system
with new operations that communicate with constraints directly rather than only
indirectly via operations on connectors.  Although it is easy to implement the
expression-oriented style in terms of the imperative implementation, it is very
difficult to do the converse.</p>
</div>
</div>
<nav class="header">
<p>
Next: <a href="3_002e4.xhtml#g_t3_002e4" accesskey="n" rel="next">3.4</a>, Prev: <a href="3_002e2.xhtml#g_t3_002e2" accesskey="p" rel="prev">3.2</a>, Up: <a href="#g_t3_002e3" accesskey="u" rel="prev">3.3</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>


</section><span class="bottom jump" title="Jump to bottom"><a href="#pagebottom" accesskey="b">⇣</a></span><a id="pagebottom"></a>
</body>
</html>
